Изменения
Нет описания правки
'''Многочлен Татта''' - — наиболее общая характеристика, описывающая комбинаторные свойства графа.
==Основное определение==
}}
Из этого определения не очевидна корректность: почему полученная функция не зависит от порядка выкидывания рёбер? Однако, если определение корректно, <tex> T_G </tex>, очевидно, является многочленом от двух переменных с целыми неотрицательными коэффициентами. Корректность мы докажем, связав многочлен Татта с другим многочленом - — ранговым многочленом Уитни (''Whitney 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> 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> 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. Следовательно, <br><center><tex> T_{Z_{n}}(x, y) = y + x + ... + x^{n - 1}</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) доказано. <br>
Рассмотрим <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).<br> Теперь необходимое тождество для полинома Татта полного графа может быть получено при подстановке равенств (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>.
==Источники информации==
* [http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Карпов Д.В. - — Теория Графов]<br />* [http://www.mathnet.ru/links/f39ceb5fdeb743a27ea1e43da2218762/mp215.pdf Бурман Ю.М. - — Многочлен Татта и модель случайных кластеров]<br />* [http://www.math.ucla.edu/~pak/papers/Pak_Computation_Tutte_polynomial_complete_graphs.pdf Igor M. Pak - — Computations of Tutte polynomial of complete graphs]<br />
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
