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

Материал из Викиконспекты
Версия от 16:49, 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]\triangleright[/math]
...
[math]\triangleleft[/math]