Изменения

Перейти к: навигация, поиск

Многочлен Татта

665 байт добавлено, 17:22, 16 декабря 2013
Многочлен Татта цикла
==Многочлен Татта цикла==
Пусть <tex> G = Z_n </tex> - цикл из <tex> n </tex> вершин. Тогда для произвольного ребра <tex> e </tex>, граф <tex> G \backslash e </tex> - цепочка <tex> L_n </tex> из <tex> n </tex>, а <tex> G/e = Z_n </tex>. По свойству 4, <tex> T_{Z_n}(x, y) = T_{L_n}(x, y) + T_{Z_{n - 1} }(x, y) = x^{n - 1} + T_{Z_{n - 1}}(x, y)</tex> - верно для всех <tex> n > 1 </tex>. При этом граф <tex> Z_1 </tex> - петля, так что <tex> T_{Z_1} = y </tex> по свойствам 1 и 3. Следовательно, <br><center><tex> T_{Z_{n}} = y + x + ... + x^{n - 1}</tex></center>
==Многочлен Татта полного графа==
Анонимный участник

Навигация