Изменения

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

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

13 байт убрано, 23:04, 21 декабря 2013
Универсальное свойство многочлена Татта
Пусть <tex> e </tex> является петлёй. Тогда <tex> \rho _2 (E \backslash {e}) = \rho (E) </tex>, так как удаление <tex> e </tex> не меняет ни числа вершин, ни числа компонент связности. Тогда <tex> f(G) = y_0f(G \backslash e) = y_0 a^{\rho _2 (E \backslash {e})} b^{|E| - 1 - \rho _2 (E \backslash {e})} T_ {G \backslash e} (\frac {x_0}{a}, \frac {y_0}{b}) = y_0 a^{\rho _2 (E \backslash {e})} b^{|E| - 1 - \rho _2 (E \backslash {e})} T_ {G \backslash e} (\frac {x_0}{a}, \frac {y_0}{b}) = \frac {y_0}{b} a^{\rho (E)} b^{|E| - \rho (E)} T_ {G \backslash e} (\frac {x_0}{a}, \frac {y_0}{b}) = a^{\rho (E)}b^{|E| - \rho (E)}T_G(\frac {x_0}{a}, \frac {y_0}{b}) </tex>.<br>
Пусть <tex> e </tex> не является ни мостом, ни петлёй. Тогда <tex> \rho _1 (E \backslash {e}) = \rho (E) - 1 </tex> и <tex> \rho _2 (E \backslash {e}) = \rho (E) </tex>. Тогда <tex> f(G) = a f(G/e) + b f(G \backslash e) = a*a^{\rho _1 (E \backslash {e})} b^{|E| - 1 - \rho _1 (E \backslash {e})} T_ {G / e} (\frac {x_0}{a}, \frac {y_0}{b}) + b*a^{\rho _2 (E \backslash {e})} b^{|E| - 1 - \rho _2 (E \backslash {e})} T_ {G \backslash e} (\frac {x_0}{a}, \frac {y_0}{b}) = </tex> <tex> a^{\rho (E)}b^{|E| - \rho (E)} (T_ {G / e} (\frac {x_0}{a}, \frac {y_0}{b}) + T_ {G \backslash e} (\frac {x_0}{a}, \frac {y_0}{b})) = a^{\rho (E)}b^{|E| - \rho (E)}T_G(\frac {x_0}{a}, \frac {y_0}{b}) </tex>. <br>
Таким образом, все случаи разобраны, и теорема доказана.
Анонимный участник

Навигация