|
|
(не показано 6 промежуточных версий 2 участников) |
Строка 3: |
Строка 3: |
| ==Основное определение== | | ==Основное определение== |
| {{Определение|definition= | | {{Определение|definition= |
− | Рассмотрим граф <tex> G </tex>, возможно c петлями и кратными рёбрами. Определим '''многочлен Татта''' (''Tutte polynomial'') <tex> T_G (x, y) </tex> следующими рекурсивными соотношениями: | + | Рассмотрим граф <tex> G </tex>, возможно c петлями и кратными рёбрами. Определим '''многочлен Татта''' (англ. ''Tutte polynomial'') <tex> T_G (x, y) </tex> следующими рекурсивными соотношениями: |
| # Если граф <tex> G </tex> не имеет рёбер, то <tex> T_G (x, y) = 1 </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) = xT_{G\backslash e} (x, y) </tex> ; |
Строка 28: |
Строка 28: |
| | | |
| {{Определение|definition= | | {{Определение|definition= |
− | '''Ранговый многочлен''' ''(Rank polynomial)'' графа <tex> G </tex> есть многочлен от двух переменных, определяемый формулой: <br> | + | '''Ранговый многочлен''' (англ. ''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> | | <center><tex dpi = "140"> R_G(u, v) = \sum\limits_{A \subset E} u^{\rho (E) - \rho (A)}v^{|A| - \rho (A)} </tex> </center> |
| }} | | }} |
Строка 94: |
Строка 94: |
| {{Определение | | {{Определение |
| |definition= | | |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> соответственно. | + | Обозначим за <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> соответственно. |
| }} | | }} |
| | | |
− | Также приведём без доказательства теорему, которая связывает многочлен Татта и понятие остовного дерева: | + | Также приведём без доказательства теорему, которая связывает многочлен Татта и понятие [[Остовные деревья: определения, лемма о безопасном ребре|остовного дерева]]: |
| | | |
| {{Теорема | | {{Теорема |
Строка 157: |
Строка 157: |
| |proof= | | |proof= |
| Воспользуемся универсальным свойством многочлена Татта для функции <tex> P_G(k) = \frac {\chi _G (k)}{k^{|V|}} </tex>. Проверим условие теоремы. <br> | | Воспользуемся универсальным свойством многочлена Татта для функции <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> 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> 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> | | Пусть ребро <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> |
Многочлен Татта — наиболее общая характеристика, описывающая комбинаторные свойства графа.
Основное определение
Определение: |
Рассмотрим граф [math] G [/math], возможно c петлями и кратными рёбрами. Определим многочлен Татта (англ. Tutte polynomial) [math] T_G (x, y) [/math] следующими рекурсивными соотношениями:
- Если граф [math] G [/math] не имеет рёбер, то [math] T_G (x, y) = 1 [/math];
- Если ребро [math] e [/math] является мостом, то [math] T_G (x, y) = xT_{G\backslash e} (x, y) [/math] ;
- Если ребро [math] e [/math] является петлей, то [math] T_G (x, y) = yT_{G/e} (x, y) [/math];
- Если ребро [math] e [/math] не является ни мостом, ни петлей то [math] T_G (x, y) = T_{G\backslash e} (x, y) + T_{G/e} (x, y) [/math];
|
Из этого определения не очевидна корректность: почему полученная функция не зависит от порядка выкидывания рёбер? Однако, если определение корректно, [math] T_G [/math], очевидно, является многочленом от двух переменных с целыми неотрицательными коэффициентами. Корректность мы докажем, связав многочлен Татта с другим многочленом — ранговым многочленом Уитни (Whitney rank polynomial).
Корректность определения, связь с ранговым многочленом
Определение: |
Пусть [math] G = (V,E) [/math] — некоторый граф. Для множества [math] A \subset E [/math] через [math] G(A) [/math] будем обозначать граф [math] (V, A) [/math]. Через [math] c(G) [/math] будем обозначать число компонент связности графа [math] G [/math]. Рангом множества [math] A [/math] будем называть число [math] \rho(A) = |V| - c(G(A)) [/math]. |
Утверждение: |
Ранг множества [math] A [/math] равен количеству рёбер в любом остовном лесе графа [math] G(A) [/math]. (под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф [math] G(B) [/math], что [math] B \subset A [/math] и [math] c(G(B)) = c(G(A)) [/math]) |
[math]\triangleright[/math] |
Действительно, в каждой компоненте связности остовного леса рёбер на одно меньше чем вершин, а общее число вершин равно [math] |V| [/math]. |
[math]\triangleleft[/math] |
Теперь определим сам ранговый многочлен:
Определение: |
Ранговый многочлен (англ. Rank polynomial) графа [math] G [/math] есть многочлен от двух переменных, определяемый формулой:
[math] R_G(u, v) = \sum\limits_{A \subset E} u^{\rho (E) - \rho (A)}v^{|A| - \rho (A)} [/math] |
Показатели в формуле раногового многочлена тоже имеют некоторый смысл. Величина [math] \rho (E) - \rho (A) [/math] равна [math] c(G(A)) - c(G) [/math], т.е. приросту числа компонент связности за счёт перехода к множеству рёбер [math] A [/math]. Мы будем обозначать эту величину через [math] \rho ^{*}(A) [/math] и называть числом важных для [math] A [/math] рёбер. (Их важно добавить к [math] A [/math], чтобы получилось столько же компонент связности, сколько было изначально).
Величину [math] |A| - \rho (A) [/math] будем называть числом лишних ребёр: именно столько рёбер можно выкинуть из множества [math] A [/math], не меняя число компонент связности. Обозначать эту величину будем через [math] \overline{\rho} (A)[/math].
Далее докажем следующую техническую лемму:
Лемма: |
Пусть фиксировано некоторое ребро [math] e \in E [/math] и множество [math] A \subset E\backslash {e}[/math]. Обозначим через [math] \rho _1(A), \rho ^{*}_{1} (A), \overline {\rho _1}(A) [/math] ранги множества [math] A [/math] в графе [math] G/e [/math], а через [math] \rho _2(A), \rho ^{*}_{2}(A), \overline {\rho _2}(A) [/math] — ранги в графе [math] G\backslash e [/math]. Тогда для множества [math] A' = A\cup {e}[/math] выполняются следующие соотношения:
- Если [math] e [/math] не петля, то [math] \rho ^{*}(A') = \rho ^{*}_{1} (A) [/math] и [math] \overline{\rho} (A') = \overline {\rho _{1}} (A) [/math];
- Если [math] e [/math] не мост, то [math] \rho ^{*}(A') = \rho ^{*}_{2} (A) [/math] и [math] \overline{\rho} (A') = \overline {\rho _{2}} (A) [/math];
- Если [math] e [/math] мост, то [math] \rho ^{*}(A') = \rho ^{*} (A) - 1 [/math] и [math] \overline{\rho} (A') = \overline {\rho} (A) [/math];
- Если [math] e [/math] петля, то [math] \rho ^{*}(A') = \rho ^{*} (A) [/math] и [math] \overline{\rho} (A') = 1 + \overline {\rho} (A) [/math].
|
Доказательство: |
[math]\triangleright[/math] |
- Стягивание ребра [math] e [/math] в любом случае не меняет числа компонент связности, поэтому [math] \rho ^{*}(A') = \rho ^{*}_{1} (A) [/math]. Если [math] e [/math] не петля, то стягивание также не меняет числа лишних рёбер, откуда [math] \overline{\rho} (A') = \overline {\rho _{1}} (A) [/math].
- Если [math] e [/math] не мост, то удаление ребра [math] e [/math] не меняет числа компонент связности, откуда [math] \rho (A) = \rho _2(A)[/math] и [math] \rho (E) = \rho _2 (E \backslash {e}) [/math]. Подставляя эти равенства в формулы для [math] \rho ^{*} [/math] и [math] \overline {\rho} [/math], получаем [math] \rho ^{*}(A') = \rho ^{*}_{2} (A) [/math] и [math] \overline{\rho} (A') = \overline {\rho _{2}} (A) [/math], что и требовалось.
- Если [math] e [/math] мост, то в графе [math] G(A') [/math] на одну компоненту связности меньше, чем в [math] G(A) [/math], откуда [math] \rho ^{*}(A') = \rho ^{*} (A) - 1 [/math]. При этом ребро [math] e [/math] не будет лишним [math] A' [/math], поэтому [math] \overline{\rho} (A') = \overline {\rho} (A) [/math].
- Если [math] e [/math] петля, то её исключение не меняет числа компонент связности, поэтому [math] \rho ^{*}(A') = \rho ^{*} (A) [/math]. По той же причине [math] e [/math] является лишним, откуда [math] \overline{\rho} (A') = 1 + \overline {\rho} (A) [/math].
|
[math]\triangleleft[/math] |
Теперь, собственно, докажем связь многочлена Татта с ранговым, откуда будет следовать корректность определения для многочлена Татта:
Теорема (Татта): |
Для любого графа [math] G [/math] выполнено равенство
[math] T_G(u + 1, v + 1) = R_G(u, v)[/math] |
Доказательство: |
[math]\triangleright[/math] |
Если граф [math] G [/math] пуст, то единственным подмножеством [math] E [/math] является пустое множество, для которого нет важных и лишних рёбер. Поэтому [math] \rho^*(\emptyset ) = \overline {\rho} (\emptyset) = 0 [/math] и [math] R_G(u, v) = 1 = T_G(u + 1, v + 1) [/math].
Пусть граф [math] G [/math] не пуст. Докажем, что для рангового многочлена выполняются соотношения Татта (из определения многочлена Татта). Выберем некоторое ребро [math] e \in E [/math] и разобьём все подмножества [math] E [/math] на пары вида [math] (A, A') [/math], где [math] e \not\in A [/math] и [math] A' = A \cup {e} [/math]. Тогда [math]
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')} )
[/math]
Далее, разберём несколько случаев:
- Пусть [math] e [/math] петля. Тогда [math] \rho ^{*}(A') = \rho ^{*} (A) [/math] и [math] \overline{\rho} (A') = 1 + \overline {\rho} (A) [/math]. Тогда [math] u^{\rho^* (A')}v^{\overline {\rho} (A')} = u^{\rho^* (A)}v^{1 + \overline {\rho} (A)} = vu^{\rho^* (A)}v^{\overline {\rho} (A)} [/math], откуда [math] u^{\rho^* (A)}v^{\overline {\rho}(A)} + u^{\rho^* (A')}v^{\overline {\rho} (A')} = (v + 1)u^{\rho^* (A)}v^{\overline {\rho} (A)} [/math]. Вынося [math] (v + 1) [/math] за скобки, получаем [math] 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)[/math]. Это соответствует первому соотношению Татта.
- Пусть [math] e [/math] мост. Тогда [math] \rho ^{*}(A) = \rho ^{*} (A') + 1 = \rho ^{*}_{1} (A') [/math] и [math] \overline{\rho} (A) = \overline {\rho} (A') = \overline {\rho _1} (A) [/math]. Отсюда [math] 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) [/math]. Это второе соотношение Татта.
- Наконец, пусть [math] e [/math] не мост и не петля. Тогда [math] 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)} [/math], откуда [math]
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) [/math]. Это третье соотношение Татта.
Таким образом, многочлен [math] R_{G}(u + 1, v + 1) [/math] удовлетворяет определению многочлена Татта, что и требовалось. |
[math]\triangleleft[/math] |
Многочлен Татта дерева
Пусть [math] G [/math] — дерево c [math] n [/math] вершинами. Тогда [math] T_G(x, y) = x^{n - 1} [/math]. Этот факт можно легко показать по индукции: в дереве любое ребро является мостом, после стягивания которого получается опять дерево с [math] n - 1 [/math] вершинами.
Многочлен Татта цикла
Пусть [math] G = Z_n [/math] — цикл из [math] n [/math] вершин. Тогда для произвольного ребра [math] e [/math], граф [math] G \backslash e [/math] — цепочка [math] L_n [/math] из [math] n [/math], а [math] G/e = Z_n [/math]. По свойству 4, [math] 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)[/math] — верно для всех [math] n \gt 1 [/math]. При этом граф [math] Z_1 [/math] — петля, так что [math] T_{Z_1} = y [/math] по свойствам 1 и 3. Следовательно,
[math] T_{Z_{n}}(x, y) = y + x + ... + x^{n - 1}[/math]
Многочлен Татта полного графа
Определение: |
Пусть [math] G = K_{n + 1} = (V, E) [/math], причём [math] V = \{0, 1, 2,...,n\} [/math]. Определим лексикографический порядок [math] \prec [/math] на множестве рёбер [math] E [/math] следующим образом: [math] (i, j) \prec (i', j') [/math], если [math] i \lt i' [/math] или [math] i = i', j = j' [/math]. |
Определение: |
Обозначим за [math] S_n [/math] множество остовных деревьев [math] T [/math] графа [math] G [/math]. Будем говорить, что ребро [math] p \in T[/math] внутренне активно (англ. internally active) в [math] T [/math], если [math] p \prec q [/math] для всех [math] q \in E \backslash t [/math], таких что [math] T \backslash p \cup {q} \in S_n[/math]. Аналогичным образом, будем говорить, что ребро [math] p \in T[/math] внешне активно (англ. externally active) в [math] T [/math], если [math] p \prec q [/math] для всех [math] q \in E \backslash T [/math], таких что [math] T \backslash q \cup {p} \in S_n[/math]. Величиной внутренней (внешней) активности будем называть число внутренне (внешне) активных элементов в [math] T [/math]; эти величины будем обозначать [math] i(T) [/math] и [math] e(T) [/math] соответственно. |
Также приведём без доказательства теорему, которая связывает многочлен Татта и понятие остовного дерева:
Теорема (Татта): |
Пусть на [math] G [/math] с множеством остовных деревьев [math] S [/math]. Тогда [math]
T_G(x, y) = \sum\limits_{T \in S} x^{i(T)}y^{e(T)}
[/math] |
Обозначение: Для простоты обозначим многочлен Татта для полного графа [math] G_{K_{n + 1}}(x, y) [/math] за [math] F_n(x, y) [/math]. Тогда имеет место следующая теорема:
Теорема (Многочлен Татта полного графа): |
[math]
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)
[/math] |
Доказательство: |
[math]\triangleright[/math] |
Зафиксируем остовное дерево [math] T \in S_n [/math]. Рассмотрим ребро [math] (0, k) \in T [/math], которое разбивает [math] T [/math] на поддеревья [math] T' [/math] и [math] T'' [/math], и при этом вершина 0 лежит в [math] T'' [/math]. Пусть [math] a = |\{j|j \in T \& j \lt k\}|[/math]. Тогда докажем следующие два утверждения:
- [math] i(T) = i(T') + \delta _{a, 0} [/math], где [math] \delta _{a, 0} [/math] — символ Кронекера
- [math] e(T) = e(T') + e(T'') + a [/math]
Понятно, что ребро [math] (j_1, j_2) \in T [/math] не может быть внутренне активным, так как [math] (0, j_1) \prec (j_1, j_2) [/math], [math] (0, j_2) \prec (j_1, j_2) [/math] и [math] T \backslash (j_1, j_2) \cup {(0, j_1)} \in S_n[/math], [math] T \backslash (j_1, j_2) \cup {(0, j_2)} \in S_n[/math]. Также ребро [math] (0, k) \in T [/math] внутренне активно в [math] T [/math] [math] \Leftrightarrow [/math] [math] a = 0 [/math], потому как если существует такая вершина [math] j \in T'' [/math], такая что [math] j \lt k [/math], то [math] (0, j) \prec (0, k) [/math] и [math] T \backslash (0, k) \cup {(0, j)} \in S_n[/math]. Таким образом равенство (1) доказано.
Рассмотрим [math] (j_1, j_2) [/math], где [math] j_1 \in T' [/math], [math] j \gt 0 [/math] и [math] j_2 \in T'' [/math]. Тогда [math] (j_1, j_2) [/math] не может быть внешне активным, так как [math] (0, k) \prec (j_1, j_2) [/math] и [math] T \backslash (j_1, j_2) \cup {(0, k)} \in S_n [/math]. Аналогично, пусть [math] j \in T'' [/math], тогда ребро [math] (0, j) [/math] — внешне активно [math] \Leftrightarrow [/math] [math] j \lt k [/math]. Таким образом мы доказали и равенство (2). Теперь необходимое тождество для полинома Татта полного графа может быть получено при подстановке равенств (1) и (2) в [math]
F_n(x, y) = \sum\limits_{T \in S} x^{i(T)}y^{e(T)}
[/math] и суммировании по всем парам поддеревьев [math] T', T'' [/math] и всем рёбрам типа [math] (0, k) [/math]. |
[math]\triangleleft[/math] |
Универсальное свойство многочлена Татта
Теорема: |
Пусть числовая функция на графах [math] f(G) [/math] обладает следующими свойствами для некоторых констант [math] a, b, x_0, y_0 [/math]:
- Если в [math] G [/math] нет рёбер, то [math] f(G) = 1 [/math]
- Если ребро [math] e [/math] является мостом, то [math] f(G) = x_0f(G/e)[/math]
- Если ребро [math] e [/math] является петлёй, то [math] f(G) = y_0f(G \backslash e)[/math]
- Если ребро [math] e [/math] не является ни мостом, ни петлёй, то [math] f(G) = af(G/e) + bf(G \backslash e) [/math].
Тогда [math] f(G) = a^{\rho (E)}b^{|E| - \rho (E)}T_G(\frac {x_0}{a}, \frac {y_0}{b}) [/math]. |
Доказательство: |
[math]\triangleright[/math] |
Для доказательства проведём индукцию по количеству рёбер. Поскольку для пустого графа [math] |E| = \rho(E) = 0 [/math], а [math] T_G = 1 [/math], то база индукции верна. Докажем переход.
Пусть [math] e [/math] является мостом. Тогда [math] \rho _1 (E \backslash {e}) = \rho (E) - 1 [/math], так как стягивание [math] e [/math] не меняет число компонент связности и уменьшает число вершин на одну. Тогда [math] 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}) = [/math] [math] 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}) [/math].
Пусть [math] e [/math] является петлёй. Тогда [math] \rho _2 (E \backslash {e}) = \rho (E) [/math], так как удаление [math] e [/math] не меняет ни числа вершин, ни числа компонент связности. Тогда [math] 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}) [/math].
Пусть [math] e [/math] не является ни мостом, ни петлёй. Тогда [math] \rho _1 (E \backslash {e}) = \rho (E) - 1 [/math] и [math] \rho _2 (E \backslash {e}) = \rho (E) [/math]. Тогда [math] f(G) = a f(G/e) + b f(G \backslash e) = a\cdot 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\cdot 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}) [/math].
Таким образом, все случаи разобраны, и теорема доказана. |
[math]\triangleleft[/math] |
Связь с хроматическим многочленом
Теорема: |
Для графа [math] G [/math] и [math] k \in N [/math] выполняется соотношение [math] \chi _G (k) = (-1)^{|V| - c(G)}k^{c(G)}T_G(1 - k, 0) [/math]. |
Доказательство: |
[math]\triangleright[/math] |
Воспользуемся универсальным свойством многочлена Татта для функции [math] P_G(k) = \frac {\chi _G (k)}{k^{|V|}} [/math]. Проверим условие теоремы.
Пусть ребро [math] e [/math] является мостом. Тогда множество вершин [math] V [/math] разбивается на два непересекающихся подмножества: [math] V_1 [/math] и [math] V_2 [/math]. Обозначим через [math] G_1 [/math] и [math] G_2 [/math] соответствующие подграфы. Их раскраски не связаны друг другом, поэтому [math] \chi_{G \backslash e} (k) = \chi_{G_1} (k) \cdot \chi_{G_2} (k) [/math]. Далее, правильная раскраска [math] G/e [/math] получается из правильных раскрасок [math] G_1 [/math] и [math] G_2 [/math], где цвета склеиваемых вершин совпадают. Можно взять любую правильную раскраску [math] G_1 [/math], для чего есть [math] \chi_{G_1} (k) [/math], а из правильных раскрасок [math] G_2 [/math] годится только доля [math] \frac {1}{k} [/math], где цвет склеиваемой вершины нужный. Таким образом, [math] \chi _{G/e}(k) = \frac {1}{k} \chi _{G_1}(k) \chi _{G_2}(k) [/math]. Далее, по рекуррентному свойству хроматического многочлена [math] \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) [/math]. Значит, [math] 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) [/math], то есть первое условие выполнено для [math] x_0 = \frac {k - 1}{k} [/math].
Пусть ребро [math] e [/math] является петлёй. Тогда правильных раскрасок нет, то есть [math] P_G (k) = 0 [/math]. Значит второе условие выполнено для [math] y_0 = 0 [/math].
Пусть ребро [math] e [/math] не является ни мостом, ни петлёй. Опять же, в силу рекуррентного свойства хроматического многочлена [math] \chi _{G}(k) = \chi _{G \backslash e}(k) + \chi _{G / e}(k) [/math]. Поделив на [math] k^{|V|} [/math], получим [math] P_G(k) = -\frac {1}{k} P_{G / e} (k) + P_{G \backslash e} (k) [/math]. Значит, третье соотношение выполнено для [math] a = \frac {1}{k}, b = 1 [/math].
Согласно универсальному свойству многочлена Татта получаем [math] P_G (k) = (-\frac {1}{k})^{\rho (E)} T_G(1 - k, 0) [/math]. Значит, [math] \chi _G (k) = (-1)^{\rho (E)}k^{|V| - \rho (E)}T_G(1 - k, 0) [/math]. Поскольку [math] \rho (E) = |V| - c(G) [/math], получаем [math] \chi _G (k) = (-1)^{|V| - c(G)}k^{c(G)}T_G(1 - k, 0) [/math]. |
[math]\triangleleft[/math] |
Значения многочлена Татта
Теорема: |
Для любого графа [math] G [/math] верно, что:
- [math] T_G (1, 1) [/math] равно количеству остовных лесов;
- [math] T_G (1, 2) [/math] равно количеству подграфов [math] G [/math], имеющих столько же компонент связности, что и [math] G [/math];
- [math] T_G (2, 1) [/math] равно количеству ациклических подграфов [math] G [/math].
|
Доказательство: |
[math]\triangleright[/math] |
Заметим, что [math] \overline {\rho} (A) = 0 [/math] тогда и только тогда, когда [math] G(A) [/math] не содержит циклов, а [math] \rho ^*(A) = 0 [/math] тогда и только тогда, когда [math] G(A) [/math] имеет столько же компонент связности, что и [math] G [/math].
Далее, воспользуемся теоремой о связи с ранговым многочленом:
- [math] T_G(1, 1) = R_G(0, 0) [/math]. Учитывая, что [math] 0^0 = 1 [/math] и [math] 0^k = 0 [/math] при [math] k \gt 0 [/math], ненулевыми (а именно единичными) будут только те слагаемые, где [math] \rho^*(A) = 0 [/math] и [math] \overline {\rho} (A) = 0 [/math]. Это означает, что [math] G(A) [/math] не содержит циклов и содержит столько же компонент связности, сколько и [math] G [/math], то есть является остовным лесом. Суммируя единицы для каждого остовного леса, получаем число остовных лесов.
- [math] T_G(1, 2) = R_G(0, 1) [/math]. Здесь мы суммируем единицы для тех [math] A [/math], где [math] \rho^*(A) = 0 [/math], то есть для подграфов имеющих столько же компонент связности, сколько и [math] G [/math].
- [math] T_G(2, 1) = R_G(1, 0) [/math]. Здесь мы суммируем единицы для тех [math] A [/math], где [math] \overline {\rho}(A) = 0 [/math], то есть для ациклических подграфов.
|
[math]\triangleleft[/math] |
Источники информации