Изменения
→Многочлен Татта полного графа
==Основное определение==
{{Определение|definition=
Рассмотрим граф <tex> G </tex>, возможно c петлями и кратными рёбрами. Определим '''многочлен Татта''' (англ. ''Tutte polynomial'') <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> ;
{{Определение|definition=
'''Ранговый многочлен''' (англ. ''Rank polynomial'') графа <tex> G </tex> есть многочлен от двух переменных, определяемый формулой: <br>
<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> 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> соответственно.
}}
Также приведём без доказательства теорему, которая связывает многочлен Татта и понятие [[Остовные деревья: определения, лемма о безопасном ребре|остовного дерева]]:
{{Теорема
|proof=
Воспользуемся универсальным свойством многочлена Татта для функции <tex> P_G(k) = \frac {\chi _G (k)}{k^{|V|}} </tex>. Проверим условие теоремы. <br>
Пусть ребро <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) \cdot \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) \cdot \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>. <br>
Пусть ребро <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>. <br>
