Многочлен Татта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Существование и единственность)
(Существование и единственность)
Строка 69: Строка 69:
  
 
# Пусть <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) </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> 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')} =
<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^{\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>. Это второе соотношение Татта.
 
(u + 1)R_{G \backslash e}(u, v) </tex>. Это второе соотношение Татта.

Версия 16:06, 16 декабря 2013

Основные определения

Определение:
Рассмотрим граф [math] G [/math], возможно петлями и кратными рёбрами. Определим многочлен Татта [math] T_G (x, y) [/math] следующими рекурсивными соотношениями:
  1. Если граф [math] G [/math] пуст, то [math] T_G (x, y) = 1 [/math];
  2. Если ребро [math] e [/math] является мостом, то [math] T_G (x, y) = xT_{G\backslash e} (x, y) [/math] ;
  3. Если ребро [math] e [/math] является петлей, то [math] T_G (x, y) = yT_{G/e} (x, y) [/math];
  4. Если ребро [math] e [/math] не является ни мостом, ни петлей то [math] T_G (x, y) = T_{G\backslash e} (x, y) + T_{G/e} (x, y) [/math];


Из этого определения не очевидна корректность: почему полученная функция не зависит от порядка выкидывания рёбер? Однако, если определение корректно, [math] T_G [/math], очевидно, является многочленом от двух переменных с целыми неотрицательными коэффициентами. Корректность мы докажем, связав многочлен Татта с другим многочленом - ранговым многочленом Уитни.

Существование и единственность

Определение:
Пусть [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]


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


Определение:
Ранговый многочлен графа [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] выполняются следующие соотношения:
  1. Если [math] e [/math] не петля, то [math] \rho ^{*}(A') = \rho ^{*}_{1} (A) [/math] и [math] \overline{\rho} (A') = \overline {\rho _{1}} (A) [/math];
  2. Если [math] e [/math] не мост, то [math] \rho ^{*}(A') = \rho ^{*}_{2} (A) [/math] и [math] \overline{\rho} (A') = \overline {\rho _{2}} (A) [/math];
  3. Если [math] e [/math] мост, то [math] \rho ^{*}(A') = \rho ^{*} (A) - 1 [/math] и [math] \overline{\rho} (A') = \overline {\rho} (A) [/math];
  4. Если [math] e [/math] петля, то [math] \rho ^{*}(A') = \rho ^{*} (A) [/math] и [math] \overline{\rho} (A') = 1 + \overline {\rho} (A) [/math].
Доказательство:
[math]\triangleright[/math]
  1. Стягивание ребра [math] e [/math] в любом случае не меняет числа компонент связности, поэтому [math] \rho ^{*}(A') = \rho ^{*}_{1} (A) [/math]. Если [math] e [/math] не петля, то стягивание также не меняет числа лишних рёбер, откуда [math] \overline{\rho} (A') = \overline {\rho _{1}} (A) [/math].
  2. Если [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], что и требовалось.
  3. Если [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].
  4. Если [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]

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

  1. Пусть [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]. Это соответствует первому соотношению Татта.
  2. Пусть [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]. Это второе соотношение Татта.
  3. AAA.
  4. Наконец, пусть [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]