Изменения
→Универсальное свойство многочлена Татта
==Универсальное свойство многочлена Татта==
{{Теорема
|statement=
Пусть числовая функция на графах <tex> f(G) </tex> обладает следующими свойствами для некоторых констант <tex> a, b, x_0, y_0 </tex>:
# Если в <tex> G <> нет рёбер, то <tex> f(G) = 1 </tex>
# Если ребро <tex> e </tex> является мостом, то <tex> f(G) = x_0f(G/e)</tex>
# Если ребро <tex> e </tex> является петлёй, то <tex> f(G) = y_0f(G \backslash e)</tex>
# Если ребро <tex> e </tex> не является ни мостом, ни петлёй, то <tex> f(G) = af(G/e) + bf(G \backslash e) </tex>.
Тогда <tex> f(G) = a^{\rho (E)}b^{|E| - \rho (E)}T_G(\frac {x_0}{a}, \frac {y_0}{b}) </tex>.
|proof=
Для доказательства проведём индукцию по количеству рёбер. Поскольку для пустого графа <tex> |E| = \rho(E) = 0 </tex>, а <tex> T_G = 1 </tex>, то база индукции верна. Докажем переход. <br>
Пусть <tex> e </tex> является мостом. Тогда <tex> \rho _1 (E \backslash {e}) = \rho (E) - 1 </tex>, так как стягивание <tex> e </tex> не меняет число компонент связности и уменьшает число вершин на одну. Тогда <tex> f(G) = x_0f(G/e) = x_0 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}) = </tex> <tex> x_0 a^{\rho (E) - 1} b^{|E| - \rho (E)} T_{G/e}(\frac {x_0}{a}, \frac {y_0}{b}) = \frac {x_0}{a} a^{\rho (E)} b^{|E| - \rho (E)} </tex><tex> T_{G/e}(\frac {x_0}{a}, \frac {y_0}{b}) = ^{\rho (E)}b^{|E| - \rho (E)}T_G(\frac {x_0}{a}, \frac {y_0}{b}) </tex>. Что и требовалось. <br>
Пусть <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})} </tex><tex> 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>. Что и требовалось.
}}
==Связь с хроматическим многочленом==
==Значение многочлена Татта для некоторых значений переменных==
