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

Материал из Викиконспекты
Версия от 23:20, 15 декабря 2013; 176.116.241.114 (обсуждение) (Существование и единственность)
Перейти к: навигация, поиск

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

Определение:
Рассмотрим граф [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] 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]
...
[math]\triangleleft[/math]