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

2013-12-21T22:17:39Z

176.116.241.114: /* Корректность определения, связь с ранговым многочленом Уитни */

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

2013-12-21T22:17:19Z

176.116.241.114:

'''Многочлен Татта графа''' - наиболее общая характеристика описывающая комбинаторные свойства графа.

==Основное определение==
{{Определение|definition=
Рассмотрим граф <tex> G </tex>, возможно c петлями и кратными рёбрами. Определим '''многочлен Татта''' <tex> T_G (x, y) </tex> следующими рекурсивными соотношениями:
# Если граф <tex> G </tex> пуст, то <tex> T_G (x, y) = 1 </tex>;
# Если ребро <tex> e </tex> является мостом, то <tex> T_G (x, y) = xT_{G\backslash e} (x, y) </tex> ;
# Если ребро <tex> e </tex> является петлей, то <tex> T_G (x, y) = yT_{G/e} (x, y) </tex>;
# Если ребро <tex> e </tex> не является ни мостом, ни петлей то <tex> T_G (x, y) = T_{G\backslash e} (x, y) + T_{G/e} (x, y) </tex>;
}}

Из этого определения не очевидна корректность: почему полученная функция не зависит от порядка выкидывания рёбер? Однако, если определение корректно, <tex> T_G </tex>, очевидно, является многочленом от двух переменных с целыми неотрицательными коэффициентами. Корректность мы докажем, связав многочлен Татта с другим многочленом - ранговым многочленом Уитни (''Whiney rank polynomial'').

==Корректность определения, связь с ранговым многочленом Уитни==
{{Определение|definition=
Пусть <tex> G = (V,E) </tex> - некоторый граф. Для множества <tex> A \subset E </tex> через <tex> G(A) </tex> будем обозначать граф <tex> (V, A) </tex>. Через <tex> c(G) </tex> будем обозначать '''число компонент связности''' графа <tex> G </tex>. '''Рангом''' множества <tex> A </tex> будем называть число <tex> \rho(A) = |V| - c(G(A)) </tex>.
}}

{{Утверждение
|statement=
Ранг множества <tex> A </tex> равен количеству рёбер в любом остовном лесе графа <tex> G(A) </tex>. (под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф <tex> G(B) </tex>, что <tex> B \subset A </tex> и <tex> c(G(B)) = c(G(A)) </tex>)
|proof=
Действительно, в каждой компоненте связности остовного леса рёбер на одно меньше чем вершин, а общее число вершин равно <tex> |V| </tex>.
}}

Теперь определим сам ранговый многочлен:

{{Определение|definition=
'''Ранговый многочлен''' графа <tex> G </tex> есть многочлен от двух переменных, определяемый формулой: 
<center><tex dpi = "140"> R_G(u, v) = \sum\limits_{A \subset E} u^{\rho (E) - \rho (A)}v^{|A| - \rho (A)} </tex> </center>
}}

{{Определение|definition=
Показатели в формуле раногового многочлена тоже имеют некоторый смысл. Величина <tex> \rho (E) - \rho (A) </tex> равна <tex> c(G(A)) - c(G) </tex>, т.е. приросту числа компонент связности за счёт перехода к множеству рёбер <tex> A </tex>. Мы будем обозначать эту величину через <tex> \rho ^{*}(A) </tex> и называть числом ''важных'' для <tex> A </tex> рёбер. (Их важно добавить к <tex> A </tex>, чтобы получилось столько же компонент связности, сколько было изначально). 
Величину <tex> |A| - \rho (A) </tex> будем называть числом ''лишних'' ребёр: именно столько рёбер можно выкинуть из множества <tex> A </tex>, не меняя число компонент связности. Обозначать эту величину будем через <tex> \overline{\rho} (A)</tex>.
}}

Далее докажем следующую техническую лемму:

{{Лемма
|statement=
Пусть фиксировано некоторое ребро <tex> e \in E </tex> и множество <tex> A \subset E\backslash {e}</tex>. Обозначим через <tex> \rho _1(A), \rho ^{*}_{1} (A), \overline {\rho _1}(A) </tex> ранги множества <tex> A </tex> в графе <tex> G/e </tex>, а через <tex> \rho _2(A), \rho ^{*}_{2}(A), \overline {\rho _2}(A) </tex> - ранги в графе <tex> G\backslash e </tex>. Тогда для множества <tex> A' = A\cup {e}</tex> выполняются следующие соотношения:
# Если <tex> e </tex> не петля, то <tex> \rho ^{*}(A') = \rho ^{*}_{1} (A) </tex> и <tex> \overline{\rho} (A') = \overline {\rho _{1}} (A) </tex>;
# Если <tex> e </tex> не мост, то <tex> \rho ^{*}(A') = \rho ^{*}_{2} (A) </tex> и <tex> \overline{\rho} (A') = \overline {\rho _{2}} (A) </tex>;
# Если <tex> e </tex> мост, то <tex> \rho ^{*}(A') = \rho ^{*} (A) - 1 </tex> и <tex> \overline{\rho} (A') = \overline {\rho} (A) </tex>;
# Если <tex> e </tex> петля, то <tex> \rho ^{*}(A') = \rho ^{*} (A) </tex> и <tex> \overline{\rho} (A') = 1 + \overline {\rho} (A) </tex>.

|proof=
# Стягивание ребра <tex> e </tex> в любом случае не меняет числа компонент связности, поэтому <tex> \rho ^{*}(A') = \rho ^{*}_{1} (A) </tex>. Если <tex> e </tex> не петля, то стягивание также не меняет числа лишних рёбер, откуда <tex> \overline{\rho} (A') = \overline {\rho _{1}} (A) </tex>.
# Если <tex> e </tex> не мост, то удаление ребра <tex> e </tex> не меняет числа компонент связности, откуда <tex> \rho (A) = \rho _2(A)</tex> и <tex> \rho (E) = \rho _2 (E \backslash {e}) </tex>. Подставляя эти равенства в формулы для <tex> \rho ^{*} </tex> и <tex> \overline {\rho} </tex>, получаем <tex> \rho ^{*}(A') = \rho ^{*}_{2} (A) </tex> и <tex> \overline{\rho} (A') = \overline {\rho _{2}} (A) </tex>, что и требовалось.
# Если <tex> e </tex> мост, то в графе <tex> G(A') </tex> на одну компоненту связности меньше, чем в <tex> G(A) </tex>, откуда <tex> \rho ^{*}(A') = \rho ^{*} (A) - 1 </tex>. При этом ребро <tex> e </tex> не будет лишним <tex> A' </tex>, поэтому <tex> \overline{\rho} (A') = \overline {\rho} (A) </tex>.
# Если <tex> e </tex> петля, то её исключение не меняет числа компонент связности, поэтому <tex> \rho ^{*}(A') = \rho ^{*} (A) </tex>. По той же причине <tex> e </tex> является лишним, откуда <tex> \overline{\rho} (A') = 1 + \overline {\rho} (A) </tex>.
}}

Теперь, собственно, докажем связь многочлена Татта с ранговым, откуда будет следовать корректность определения для многочлена Татта:

{{Теорема
|about=
Татта
|statement=
Для любого графа <tex> G </tex> выполнено равенство <center><tex> T_G(u + 1, v + 1) = R_G(u, v)</tex></center>

|proof=
Если граф <tex> G </tex> пуст, то единственным подмножеством <tex> E </tex> является пустое множество, для которого нет важных и лишних рёбер. Поэтому <tex> \rho^*(\emptyset ) = \overline {\rho} (\emptyset) = 0 </tex> и <tex> R_G(u, v) = 1 = T_G(u + 1, v + 1) </tex>. 
Пусть граф <tex> G </tex> не пуст. Докажем, что для рангового многочлена выполняются соотношения Татта (из определения многочлена Татта). Выберем некоторое ребро <tex> e \in E </tex> и разобьём все подмножества <tex> E </tex> на пары вида <tex> (A, A') </tex>, где <tex> e \not\in A </tex> и <tex> A' = A \cup {e} </tex>. Тогда <center><tex dpi = "130">
R_G(u, v) = \sum\limits_{A \subset {E \backslash {e}}} ( u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho} (A')} )
</tex></center>

Далее, разберём несколько случаев:

# Пусть <tex> e </tex> петля. Тогда <tex> \rho ^{*}(A') = \rho ^{*} (A) </tex> и <tex> \overline{\rho} (A') = 1 + \overline {\rho} (A) </tex>. Тогда <tex> u^{\rho^* (A')}v^{\overline {\rho} (A')} = u^{\rho^* (A)}v^{1 + \overline {\rho} (A)} = vu^{\rho^* (A)}v^{\overline {\rho} (A)} </tex>, откуда <tex> u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho} (A')} = (v + 1)u^{\rho^* (A)}v^{\overline {\rho} (A)} </tex>. Вынося <tex> (v + 1) </tex> за скобки, получаем <tex> R_G(u, v) = (v + 1)\sum\limits_{A \subset {E \backslash {e}}} u^{\rho^* (A)}v^{\overline {\rho}(A)} = (v + 1) R_{G \backslash e}(u, v)</tex>. Это соответствует первому соотношению Татта.
# Пусть <tex> e </tex> мост. Тогда <tex> \rho ^{*}(A) = \rho ^{*} (A') + 1 = \rho ^{*}_{1} (A') </tex> и <tex> \overline{\rho} (A) = \overline {\rho} (A') = \overline {\rho _1} (A) </tex>. Отсюда <tex> u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho}(A')} =
u^{\rho^{*}_{1} (A) + 1}v^{\overline {\rho _1}(A)} + u^{\rho ^{*}_{1} (A)}v^{\overline{\rho _{1}}(A)} =
(u + 1)R_{G \backslash e}(u, v) </tex>. Это второе соотношение Татта.
# Наконец, пусть <tex> e </tex> не мост и не петля. Тогда <tex> u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho}(A')} = u^{\rho ^{*}_{2} (A)}v^{\overline {\rho _2}(A)} + u^{\rho ^{*}_{1} (A)}v^{\overline {\rho _1}(A)} </tex>, откуда <tex>
R_{G}(u, v) = \sum\limits_{A \subset {E \backslash {e}}} u^{\rho ^{*}_{2} (A)}v^{\overline {\rho _2}(A)} + \sum\limits_{A \subset {E \backslash {e}}} u^{\rho ^{*}_{1} (A)}v^{\overline {\rho _1}(A)} = R_{G \backslash e}(u, v) + R_{G / e}(u, v) </tex>. Это третье соотношение Татта. 
Таким образом, многочлен <tex> R_{G}(u + 1, v + 1) </tex> удовлетворяет определению многочлена Татта, что и требовалось.

}}

==Многочлен Татта дерева==
Пусть <tex> G </tex> - дерево c <tex> n </tex> вершинами. Тогда <tex> T_G(x, y) = x^{n - 1} </tex>. Этот факт можно легко показать по индукции: в дереве любое ребро является мостом, после стягивания которого получается опять дерево с <tex> n - 1 </tex> вершинами.

==Многочлен Татта цикла==
Пусть <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. Следовательно, <center><tex> T_{Z_{n}}(x, y) = y + x + ... + x^{n - 1}</tex></center>

==Многочлен Татта полного графа==

{{Определение
|definition=
Пусть <tex> G = K_{n + 1} = (V, E) </tex>, <tex> V = {0, 1, 2,...,n} </tex> и <tex> E = 2^{V} </tex>. Определим лексикографический порядок <tex> \prec </tex> на множестве рёбер <tex> E </tex> следующим образом: <tex> (i, j) \prec (i', j') </tex>, если <tex> i < i' </tex> или <tex> i = i', j = j' </tex>.
}}

{{Определение
|definition=
Обозначим за <tex> S_n </tex> множество остовных деревьев <tex> T </tex> графа <tex> G </tex>. Будем говорить, что ребро <tex> p \in T</tex> '''внутренне активно'''(internally active) в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash t </tex>, таких что <tex> T \backslash p \cup {q} \in S_n</tex>. Аналогичным образом, будем говорить, что ребро <tex> p \in T</tex> '''внешне активно'''(externally active) в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash T </tex>, таких что <tex> T \backslash q \cup {p} \in S_n</tex>. Величиной внутренней (внешней) активности будем называть число внутренне (внешне) активных элементов в <tex> T </tex>; эти величины будем обозначать <tex> i(T) </tex> и <tex> e(T) </tex> соответственно.
}}

Также приведём без доказательства теорему, которая связывает многочлен Татта и понятие остовного дерева:

{{Теорема
|about=
Татта
|statement=
Пусть на <tex> G </tex> с множеством остовных деревьев <tex> S </tex>. Тогда <tex>
T_G(x, y) = \sum\limits_{T \in S} x^{i(T)}y^{e(T)}
</tex>
}}

'''Обозначение:''' Для простоты обозначим многочлен Татта для полного графа <tex> G_{K_{n + 1}}(x, y) </tex> за <tex> F_n(x, y) </tex>. Тогда имеет место следующая теорема:
{{Теорема
|about=
Многочлен Татта полного графа
|statement=
<center><tex>
F_{n}(x, y) = \sum \limits_{k = 1}^n {n - 1 \choose k - 1} (x + y + y^2 + ... + y^{k - 1}) F_{k - 1}(1, y)F_{n - k} (x, y)
</tex></center>

|proof=
Зафиксируем остовное дерево <tex> T \in S_n </tex>. Рассмотрим ребро <tex> (0, k) \in T </tex>, которое разбивает <tex> T </tex> на поддеревья <tex> T' </tex> и <tex> T'' </tex>, и при этом вершина 0 лежит в <tex> T'' </tex>. Пусть <tex> a = |\{j|j \in T \& j < k\}|</tex>. Тогда докажем следующие два утверждения:
# <tex> i(T) = i(T') + \delta _{a, 0} </tex>, где <tex> \delta _{a, 0} </tex> - символ Кронекера
# <tex> e(T) = e(T') + e(T'') + a </tex>
Понятно, что ребро <tex> (j_1, j_2) \in T </tex> не может быть ''внутренне'' активным, так как <tex> (0, j_1) \prec (j_1, j_2) </tex>, <tex> (0, j_2) \prec (j_1, j_2) </tex> и <tex> T \backslash (j_1, j_2) \cup {(0, j_1)} \in S_n</tex>, <tex> T \backslash (j_1, j_2) \cup {(0, j_2)} \in S_n</tex>. Также ребро <tex> (0, k) \in T </tex> внутренне активно в <tex> T </tex> <tex> \Leftrightarrow </tex> <tex> a = 0 </tex>, потому как если существует такая вершина <tex> j \in T'' </tex>, такая что <tex> j < k </tex>, то <tex> (0, j) \prec (0, k) </tex> и <tex> T \backslash (0, k) \cup {(0, j)} \in S_n</tex>. Таким образом равенство (1) доказано. 
Рассмотрим <tex> (j_1, j_2) </tex>, где <tex> j_1 \in T' </tex>, <tex> j > 0 </tex> и <tex> j_2 \in T'' </tex>. Тогда <tex> (j_1, j_2) </tex> не может быть ''внешне'' активным, так как <tex> (0, k) \prec (j_1, j_2) </tex> и <tex> T \backslash (j_1, j_2) \cup {(0, k)} \in S_n </tex>. Аналогично, пусть <tex> j \in T'' </tex>, тогда ребро <tex> (0, j) </tex> - внешне активно <tex> \Leftrightarrow </tex> <tex> j < k </tex>. Таким образом мы доказали и равенство (2). Теперь необходимое тождество для полинома Татта полного графа может быть получено при подстановке равенств (1) и (2) в <tex>
F_n(x, y) = \sum\limits_{T \in S} x^{i(T)}y^{e(T)}
</tex> и суммировании по всем парам поддеревьев <tex> T', T'' </tex> и всем рёбрам типа <tex> (0, k) </tex>.
}}

==Универсальное свойство многочлена Татта==
{{Теорема
|statement=
Пусть числовая функция на графах <tex> f(G) </tex> обладает следующими свойствами для некоторых констант <tex> a, b, x_0, y_0 </tex>:
# Если в <tex> G </tex> нет рёбер, то <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 dpi = "130"> 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>, то база индукции верна. Докажем переход. 

Пусть <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)} T_{G/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>. 

Пусть <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>. 

Пусть <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}) = 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>. 
Таким образом, все случаи разобраны, и теорема доказана.

}}

==Связь с хроматическим многочленом==

{{Теорема
|statement=
Для графа <tex> G </tex> и <tex> k \in N </tex> выполняется соотношение <tex> \chi _G (k) = (-1)^{|V| - c(G)}k^{c(G)}T_G(1 - k, 0) </tex>.
|proof=
Воспользуемся универсальным свойством многочлена Татта для функции <tex> P_G(k) = \frac {\chi _G (k)}{k^{|V|}} </tex>. Проверим условие теоремы. 
Пусть ребро <tex> e </tex> является мостом. Тогда множество вершин <tex> V </tex> разбивается на два непересекающихся подмножества: <tex> V_1 </tex> и <tex> V_2 </tex>. Обозначим через <tex> G_1 </tex> и <tex> G_2 </tex> соответствующие подграфы. Их раскраски не связаны друг другом, поэтому <tex> \chi_{G \backslash e} (k) = \chi_{G_1} (k) * \chi_{G_2} (k) </tex>. Далее, правильная раскраска <tex> G/e </tex> получается из правильных раскрасок <tex> G_1 </tex> и <tex> G_2 </tex>, где цвета склеиваемых вершин совпадают. Можно взять любую правильную раскраску <tex> G_1 </tex>, для чего есть <tex> \chi_{G_1} (k) </tex>, а из правильных раскрасок <tex> G_2 </tex> годится только доля <tex> \frac {1}{k} </tex>, где цвет склеиваемой вершины нужный. Таким образом, <tex> \chi _{G/e}(k) = \frac {1}{k} \chi _{G_1}(k) \chi _{G_2}(k) </tex>. Далее, по рекуррентному свойству хроматического многочлена <tex> \chi _{G}(k) = \chi _{G \backslash e}(k) - \chi _{G / e}(k) = (1 - \frac {1}{k})\chi _{G_1}(k)*\chi _{G_2}(k) = (k - 1)\chi _{G / e}(k) </tex>. Значит, <tex> P_G (k) = \frac {\chi _{G}(k)}{k^{|V|}} = \frac {(k - 1)\chi _{G / e}(k)}{k^{|V|}} = \frac {k - 1}{k} P_{G / e} (k) </tex>, то есть первое условие выполнено для <tex> x_0 = \frac {k - 1}{k} </tex>. 
Пусть ребро <tex> e </tex> является петлёй. Тогда правильных раскрасок нет, то есть <tex> P_G (k) = 0 </tex>. Значит второе условие выполнено для <tex> y_0 = 0 </tex>.
Пусть ребро <tex> e </tex> не является ни мостом, ни петлёй. Опять же, в силу рекуррентного свойства хроматического многочлена <tex> \chi _{G}(k) = \chi _{G \backslash e}(k) + \chi _{G / e}(k) </tex>. Поделив на <tex> k^{|V|} </tex>, получим <tex> P_G(k) = -\frac {1}{k} P_{G / e} (k) + P_{G \backslash e} (k) </tex>. Значит, третье соотношение выполнено для <tex> a = \frac {1}{k}, b = 1 </tex>. 
Согласно универсальному свойству многочлена Татта получаем <tex> P_G (k) = (-\frac {1}{k})^{\rho (E)} T_G(1 - k, 0) </tex>. Значит, <tex> \chi _G (k) = (-1)^{\rho (E)}k^{|V| - \rho (E)}T_G(1 - k, 0) </tex>. Поскольку <tex> \rho (E) = |V| - c(G) </tex>, получаем <tex> \chi _G (k) = (-1)^{|V| - c(G)}k^{c(G)}T_G(1 - k, 0) </tex>.
}}

==Значения многочлена Татта==
{{Теорема
|statement=
Для любого графа <tex> G </tex> верно, что:
# <tex> T_G (1, 1) </tex> равно количеству остовных лесов;
# <tex> T_G (1, 2) </tex> равно количеству подграфов <tex> G </tex>, имеющих столько же компонент связности, что и <tex> G </tex>;
# <tex> T_G (2, 1) </tex> равно количеству ациклических подграфов <tex> G </tex>.
|proof=
Заметим, что <tex> \overline {\rho} (A) = 0 </tex> тогда и только тогда, когда <tex> G(A) </tex> не содержит циклов, а <tex> \rho ^*(A) = 0 </tex> тогда и только тогда, когда <tex> G(A) </tex> имеет столько же компонент связности, что и <tex> G </tex>. 
Далее, воспользуемся теоремой о связи с ранговым многочленом:
# <tex> T_G(1, 1) = R_G(0, 0) </tex>. Учитывая, что <tex> 0^0 = 1 </tex> и <tex> 0^k = 0 </tex> при <tex> k > 0 </tex>, ненулевыми (а, именно, единичными) будут только те слагаемые, где <tex> \rho^*(A) = 0 </tex> и <tex> \overline {\rho} (A) = 0 </tex>. Это означает, что <tex> G(A) </tex> не содержит циклов и содержит столько же компонент связности, сколько и <tex> G </tex>, то есть является остовным лесом. Суммируя единицы для каждого остовного леса, получаем число остовных лесов.
# <tex> T_G(1, 2) = R_G(0, 1) </tex>. Здесь мы суммируем единицы для тех <tex> A </tex>, где <tex> \rho^*(A) = 0 </tex>, то есть для подграфов имеющих столько же компонент связности, сколько и <tex> G </tex>.
# <tex> T_G(2, 1) = R_G(1, 0) </tex>. Здесь мы суммируем единицы для тех <tex> A </tex>, где <tex> \overline {\rho}(A) = 0 </tex>, то есть для ациклических подграфов.

}}

2013-12-21T21:39:26Z

176.116.241.114: /* Многочлен Татта полного графа */

==Основное определение==
{{Определение|definition=
Рассмотрим граф <tex> G </tex>, возможно c петлями и кратными рёбрами. Определим '''многочлен Татта''' <tex> T_G (x, y) </tex> следующими рекурсивными соотношениями:
# Если граф <tex> G </tex> пуст, то <tex> T_G (x, y) = 1 </tex>;
# Если ребро <tex> e </tex> является мостом, то <tex> T_G (x, y) = xT_{G\backslash e} (x, y) </tex> ;
# Если ребро <tex> e </tex> является петлей, то <tex> T_G (x, y) = yT_{G/e} (x, y) </tex>;
# Если ребро <tex> e </tex> не является ни мостом, ни петлей то <tex> T_G (x, y) = T_{G\backslash e} (x, y) + T_{G/e} (x, y) </tex>;
}}

Из этого определения не очевидна корректность: почему полученная функция не зависит от порядка выкидывания рёбер? Однако, если определение корректно, <tex> T_G </tex>, очевидно, является многочленом от двух переменных с целыми неотрицательными коэффициентами. Корректность мы докажем, связав многочлен Татта с другим многочленом - ранговым многочленом Уитни (''Whiney rank polynomial'').

==Корректность определения, связь с ранговым многочленом==
{{Определение|definition=
Пусть <tex> G = (V,E) </tex> - некоторый граф. Для множества <tex> A \subset E </tex> через <tex> G(A) </tex> будем обозначать граф <tex> (V, A) </tex>. Через <tex> c(G) </tex> будем обозначать '''число компонент связности''' графа <tex> G </tex>. '''Рангом''' множества <tex> A </tex> будем называть число <tex> \rho(A) = |V| - c(G(A)) </tex>.
}}

{{Утверждение
|statement=
Ранг множества <tex> A </tex> равен количеству рёбер в любом остовном лесе графа <tex> G(A) </tex>. (под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф <tex> G(B) </tex>, что <tex> B \subset A </tex> и <tex> c(G(B)) = c(G(A)) </tex>)
|proof=
Действительно, в каждой компоненте связности остовного леса рёбер на одно меньше чем вершин, а общее число вершин равно <tex> |V| </tex>.
}}

Теперь определим сам ранговый многочлен:

{{Определение|definition=
'''Ранговый многочлен''' графа <tex> G </tex> есть многочлен от двух переменных, определяемый формулой: 
<center><tex dpi = "140"> R_G(u, v) = \sum\limits_{A \subset E} u^{\rho (E) - \rho (A)}v^{|A| - \rho (A)} </tex> </center>
}}

{{Определение|definition=
Показатели в формуле раногового многочлена тоже имеют некоторый смысл. Величина <tex> \rho (E) - \rho (A) </tex> равна <tex> c(G(A)) - c(G) </tex>, т.е. приросту числа компонент связности за счёт перехода к множеству рёбер <tex> A </tex>. Мы будем обозначать эту величину через <tex> \rho ^{*}(A) </tex> и называть числом ''важных'' для <tex> A </tex> рёбер. (Их важно добавить к <tex> A </tex>, чтобы получилось столько же компонент связности, сколько было изначально). 
Величину <tex> |A| - \rho (A) </tex> будем называть числом ''лишних'' ребёр: именно столько рёбер можно выкинуть из множества <tex> A </tex>, не меняя число компонент связности. Обозначать эту величину будем через <tex> \overline{\rho} (A)</tex>.
}}

Далее докажем следующую техническую лемму:

{{Лемма
|statement=
Пусть фиксировано некоторое ребро <tex> e \in E </tex> и множество <tex> A \subset E\backslash {e}</tex>. Обозначим через <tex> \rho _1(A), \rho ^{*}_{1} (A), \overline {\rho _1}(A) </tex> ранги множества <tex> A </tex> в графе <tex> G/e </tex>, а через <tex> \rho _2(A), \rho ^{*}_{2}(A), \overline {\rho _2}(A) </tex> - ранги в графе <tex> G\backslash e </tex>. Тогда для множества <tex> A' = A\cup {e}</tex> выполняются следующие соотношения:
# Если <tex> e </tex> не петля, то <tex> \rho ^{*}(A') = \rho ^{*}_{1} (A) </tex> и <tex> \overline{\rho} (A') = \overline {\rho _{1}} (A) </tex>;
# Если <tex> e </tex> не мост, то <tex> \rho ^{*}(A') = \rho ^{*}_{2} (A) </tex> и <tex> \overline{\rho} (A') = \overline {\rho _{2}} (A) </tex>;
# Если <tex> e </tex> мост, то <tex> \rho ^{*}(A') = \rho ^{*} (A) - 1 </tex> и <tex> \overline{\rho} (A') = \overline {\rho} (A) </tex>;
# Если <tex> e </tex> петля, то <tex> \rho ^{*}(A') = \rho ^{*} (A) </tex> и <tex> \overline{\rho} (A') = 1 + \overline {\rho} (A) </tex>.

|proof=
# Стягивание ребра <tex> e </tex> в любом случае не меняет числа компонент связности, поэтому <tex> \rho ^{*}(A') = \rho ^{*}_{1} (A) </tex>. Если <tex> e </tex> не петля, то стягивание также не меняет числа лишних рёбер, откуда <tex> \overline{\rho} (A') = \overline {\rho _{1}} (A) </tex>.
# Если <tex> e </tex> не мост, то удаление ребра <tex> e </tex> не меняет числа компонент связности, откуда <tex> \rho (A) = \rho _2(A)</tex> и <tex> \rho (E) = \rho _2 (E \backslash {e}) </tex>. Подставляя эти равенства в формулы для <tex> \rho ^{*} </tex> и <tex> \overline {\rho} </tex>, получаем <tex> \rho ^{*}(A') = \rho ^{*}_{2} (A) </tex> и <tex> \overline{\rho} (A') = \overline {\rho _{2}} (A) </tex>, что и требовалось.
# Если <tex> e </tex> мост, то в графе <tex> G(A') </tex> на одну компоненту связности меньше, чем в <tex> G(A) </tex>, откуда <tex> \rho ^{*}(A') = \rho ^{*} (A) - 1 </tex>. При этом ребро <tex> e </tex> не будет лишним <tex> A' </tex>, поэтому <tex> \overline{\rho} (A') = \overline {\rho} (A) </tex>.
# Если <tex> e </tex> петля, то её исключение не меняет числа компонент связности, поэтому <tex> \rho ^{*}(A') = \rho ^{*} (A) </tex>. По той же причине <tex> e </tex> является лишним, откуда <tex> \overline{\rho} (A') = 1 + \overline {\rho} (A) </tex>.
}}

Теперь, собственно, докажем связь многочлена Татта с ранговым, откуда будет следовать корректность определения для многочлена Татта:

{{Теорема
|about=
Татта
|statement=
Для любого графа <tex> G </tex> выполнено равенство <center><tex> T_G(u + 1, v + 1) = R_G(u, v)</tex></center>

|proof=
Если граф <tex> G </tex> пуст, то единственным подмножеством <tex> E </tex> является пустое множество, для которого нет важных и лишних рёбер. Поэтому <tex> \rho^*(\emptyset ) = \overline {\rho} (\emptyset) = 0 </tex> и <tex> R_G(u, v) = 1 = T_G(u + 1, v + 1) </tex>. 
Пусть граф <tex> G </tex> не пуст. Докажем, что для рангового многочлена выполняются соотношения Татта (из определения многочлена Татта). Выберем некоторое ребро <tex> e \in E </tex> и разобьём все подмножества <tex> E </tex> на пары вида <tex> (A, A') </tex>, где <tex> e \not\in A </tex> и <tex> A' = A \cup {e} </tex>. Тогда <center><tex dpi = "130">
R_G(u, v) = \sum\limits_{A \subset {E \backslash {e}}} ( u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho} (A')} )
</tex></center>

Далее, разберём несколько случаев:

# Пусть <tex> e </tex> петля. Тогда <tex> \rho ^{*}(A') = \rho ^{*} (A) </tex> и <tex> \overline{\rho} (A') = 1 + \overline {\rho} (A) </tex>. Тогда <tex> u^{\rho^* (A')}v^{\overline {\rho} (A')} = u^{\rho^* (A)}v^{1 + \overline {\rho} (A)} = vu^{\rho^* (A)}v^{\overline {\rho} (A)} </tex>, откуда <tex> u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho} (A')} = (v + 1)u^{\rho^* (A)}v^{\overline {\rho} (A)} </tex>. Вынося <tex> (v + 1) </tex> за скобки, получаем <tex> R_G(u, v) = (v + 1)\sum\limits_{A \subset {E \backslash {e}}} u^{\rho^* (A)}v^{\overline {\rho}(A)} = (v + 1) R_{G \backslash e}(u, v)</tex>. Это соответствует первому соотношению Татта.
# Пусть <tex> e </tex> мост. Тогда <tex> \rho ^{*}(A) = \rho ^{*} (A') + 1 = \rho ^{*}_{1} (A') </tex> и <tex> \overline{\rho} (A) = \overline {\rho} (A') = \overline {\rho _1} (A) </tex>. Отсюда <tex> u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho}(A')} =
u^{\rho^{*}_{1} (A) + 1}v^{\overline {\rho _1}(A)} + u^{\rho ^{*}_{1} (A)}v^{\overline{\rho _{1}}(A)} =
(u + 1)R_{G \backslash e}(u, v) </tex>. Это второе соотношение Татта.
# Наконец, пусть <tex> e </tex> не мост и не петля. Тогда <tex> u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho}(A')} = u^{\rho ^{*}_{2} (A)}v^{\overline {\rho _2}(A)} + u^{\rho ^{*}_{1} (A)}v^{\overline {\rho _1}(A)} </tex>, откуда <tex>
R_{G}(u, v) = \sum\limits_{A \subset {E \backslash {e}}} u^{\rho ^{*}_{2} (A)}v^{\overline {\rho _2}(A)} + \sum\limits_{A \subset {E \backslash {e}}} u^{\rho ^{*}_{1} (A)}v^{\overline {\rho _1}(A)} = R_{G \backslash e}(u, v) + R_{G / e}(u, v) </tex>. Это третье соотношение Татта. 
Таким образом, многочлен <tex> R_{G}(u + 1, v + 1) </tex> удовлетворяет определению многочлена Татта, что и требовалось.

}}

==Многочлен Татта дерева==
Пусть <tex> G </tex> - дерево c <tex> n </tex> вершинами. Тогда <tex> T_G(x, y) = x^{n - 1} </tex>. Этот факт можно легко показать по индукции: в дереве любое ребро является мостом, после стягивания которого получается опять дерево с <tex> n - 1 </tex> вершинами.

==Многочлен Татта цикла==
Пусть <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. Следовательно, <center><tex> T_{Z_{n}}(x, y) = y + x + ... + x^{n - 1}</tex></center>

==Многочлен Татта полного графа==

{{Определение
|definition=
Пусть <tex> G = K_{n + 1} = (V, E) </tex>, <tex> V = {0, 1, 2,...,n} </tex> и <tex> E = 2^{V} </tex>. Определим лексикографический порядок <tex> \prec </tex> на множестве рёбер <tex> E </tex> следующим образом: <tex> (i, j) \prec (i', j') </tex>, если <tex> i < i' </tex> или <tex> i = i', j = j' </tex>.
}}

{{Определение
|definition=
Обозначим за <tex> S_n </tex> множество остовных деревьев <tex> T </tex> графа <tex> G </tex>. Будем говорить, что ребро <tex> p \in T</tex> '''внутренне активно'''(internally active) в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash t </tex>, таких что <tex> T \backslash p \cup {q} \in S_n</tex>. Аналогичным образом, будем говорить, что ребро <tex> p \in T</tex> '''внешне активно'''(externally active) в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash T </tex>, таких что <tex> T \backslash q \cup {p} \in S_n</tex>. Величиной внутренней (внешней) активности будем называть число внутренне (внешне) активных элементов в <tex> T </tex>; эти величины будем обозначать <tex> i(T) </tex> и <tex> e(T) </tex> соответственно.
}}

Также приведём без доказательства теорему, которая связывает многочлен Татта и понятие остовного дерева:

{{Теорема
|about=
Татта
|statement=
Пусть на <tex> G </tex> с множеством остовных деревьев <tex> S </tex>. Тогда <tex>
T_G(x, y) = \sum\limits_{T \in S} x^{i(T)}y^{e(T)}
</tex>
}}

'''Обозначение:''' Для простоты обозначим многочлен Татта для полного графа <tex> G_{K_{n + 1}}(x, y) </tex> за <tex> F_n(x, y) </tex>. Тогда имеет место следующая теорема:
{{Теорема
|about=
Многочлен Татта полного графа
|statement=
<center><tex>
F_{n}(x, y) = \sum \limits_{k = 1}^n {n - 1 \choose k - 1} (x + y + y^2 + ... + y^{k - 1}) F_{k - 1}(1, y)F_{n - k} (x, y)
</tex></center>

|proof=
Зафиксируем остовное дерево <tex> T \in S_n </tex>. Рассмотрим ребро <tex> (0, k) \in T </tex>, которое разбивает <tex> T </tex> на поддеревья <tex> T' </tex> и <tex> T'' </tex>, и при этом вершина 0 лежит в <tex> T'' </tex>. Пусть <tex> a = |\{j|j \in T \& j < k\}|</tex>. Тогда докажем следующие два утверждения:
# <tex> i(T) = i(T') + \delta _{a, 0} </tex>, где <tex> \delta _{a, 0} </tex> - символ Кронекера
# <tex> e(T) = e(T') + e(T'') + a </tex>
Понятно, что ребро <tex> (j_1, j_2) \in T </tex> не может быть ''внутренне'' активным, так как <tex> (0, j_1) \prec (j_1, j_2) </tex>, <tex> (0, j_2) \prec (j_1, j_2) </tex> и <tex> T \backslash (j_1, j_2) \cup {(0, j_1)} \in S_n</tex>, <tex> T \backslash (j_1, j_2) \cup {(0, j_2)} \in S_n</tex>. Также ребро <tex> (0, k) \in T </tex> внутренне активно в <tex> T </tex> <tex> \Leftrightarrow </tex> <tex> a = 0 </tex>, потому как если существует такая вершина <tex> j \in T'' </tex>, такая что <tex> j < k </tex>, то <tex> (0, j) \prec (0, k) </tex> и <tex> T \backslash (0, k) \cup {(0, j)} \in S_n</tex>. Таким образом равенство (1) доказано. 
Рассмотрим <tex> (j_1, j_2) </tex>, где <tex> j_1 \in T' </tex>, <tex> j > 0 </tex> и <tex> j_2 \in T'' </tex>. Тогда <tex> (j_1, j_2) </tex> не может быть ''внешне'' активным, так как <tex> (0, k) \prec (j_1, j_2) </tex> и <tex> T \backslash (j_1, j_2) \cup {(0, k)} \in S_n </tex>. Аналогично, пусть <tex> j \in T'' </tex>, тогда ребро <tex> (0, j) </tex> - внешне активно <tex> \Leftrightarrow </tex> <tex> j < k </tex>. Таким образом мы доказали и равенство (2). Теперь необходимое тождество для полинома Татта полного графа может быть получено при подстановке равенств (1) и (2) в <tex>
F_n(x, y) = \sum\limits_{T \in S} x^{i(T)}y^{e(T)}
</tex> и суммировании по всем парам поддеревьев <tex> T', T'' </tex> и всем рёбрам типа <tex> (0, k) </tex>.
}}

==Универсальное свойство многочлена Татта==
{{Теорема
|statement=
Пусть числовая функция на графах <tex> f(G) </tex> обладает следующими свойствами для некоторых констант <tex> a, b, x_0, y_0 </tex>:
# Если в <tex> G </tex> нет рёбер, то <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 dpi = "130"> 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>, то база индукции верна. Докажем переход. 

Пусть <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)} T_{G/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>. 

Пусть <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>. 

Пусть <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}) = 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>. 
Таким образом, все случаи разобраны, и теорема доказана.

}}

==Связь с хроматическим многочленом==

{{Теорема
|statement=
Для графа <tex> G </tex> и <tex> k \in N </tex> выполняется соотношение <tex> \chi _G (k) = (-1)^{|V| - c(G)}k^{c(G)}T_G(1 - k, 0) </tex>.
|proof=
Воспользуемся универсальным свойством многочлена Татта для функции <tex> P_G(k) = \frac {\chi _G (k)}{k^{|V|}} </tex>. Проверим условие теоремы. 
Пусть ребро <tex> e </tex> является мостом. Тогда множество вершин <tex> V </tex> разбивается на два непересекающихся подмножества: <tex> V_1 </tex> и <tex> V_2 </tex>. Обозначим через <tex> G_1 </tex> и <tex> G_2 </tex> соответствующие подграфы. Их раскраски не связаны друг другом, поэтому <tex> \chi_{G \backslash e} (k) = \chi_{G_1} (k) * \chi_{G_2} (k) </tex>. Далее, правильная раскраска <tex> G/e </tex> получается из правильных раскрасок <tex> G_1 </tex> и <tex> G_2 </tex>, где цвета склеиваемых вершин совпадают. Можно взять любую правильную раскраску <tex> G_1 </tex>, для чего есть <tex> \chi_{G_1} (k) </tex>, а из правильных раскрасок <tex> G_2 </tex> годится только доля <tex> \frac {1}{k} </tex>, где цвет склеиваемой вершины нужный. Таким образом, <tex> \chi _{G/e}(k) = \frac {1}{k} \chi _{G_1}(k) \chi _{G_2}(k) </tex>. Далее, по рекуррентному свойству хроматического многочлена <tex> \chi _{G}(k) = \chi _{G \backslash e}(k) - \chi _{G / e}(k) = (1 - \frac {1}{k})\chi _{G_1}(k)*\chi _{G_2}(k) = (k - 1)\chi _{G / e}(k) </tex>. Значит, <tex> P_G (k) = \frac {\chi _{G}(k)}{k^{|V|}} = \frac {(k - 1)\chi _{G / e}(k)}{k^{|V|}} = \frac {k - 1}{k} P_{G / e} (k) </tex>, то есть первое условие выполнено для <tex> x_0 = \frac {k - 1}{k} </tex>. 
Пусть ребро <tex> e </tex> является петлёй. Тогда правильных раскрасок нет, то есть <tex> P_G (k) = 0 </tex>. Значит второе условие выполнено для <tex> y_0 = 0 </tex>.
Пусть ребро <tex> e </tex> не является ни мостом, ни петлёй. Опять же, в силу рекуррентного свойства хроматического многочлена <tex> \chi _{G}(k) = \chi _{G \backslash e}(k) + \chi _{G / e}(k) </tex>. Поделив на <tex> k^{|V|} </tex>, получим <tex> P_G(k) = -\frac {1}{k} P_{G / e} (k) + P_{G \backslash e} (k) </tex>. Значит, третье соотношение выполнено для <tex> a = \frac {1}{k}, b = 1 </tex>. 
Согласно универсальному свойству многочлена Татта получаем <tex> P_G (k) = (-\frac {1}{k})^{\rho (E)} T_G(1 - k, 0) </tex>. Значит, <tex> \chi _G (k) = (-1)^{\rho (E)}k^{|V| - \rho (E)}T_G(1 - k, 0) </tex>. Поскольку <tex> \rho (E) = |V| - c(G) </tex>, получаем <tex> \chi _G (k) = (-1)^{|V| - c(G)}k^{c(G)}T_G(1 - k, 0) </tex>.
}}

==Значение многочлена Татта для некоторых значений переменных==