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

Материал из Викиконспекты
Версия от 16:36, 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]


Шаблон:Определен