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

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

Определение:

Рассмотрим граф [math] G [/math], возможно петлями и кратными рёбрами. Определим многочлен Татта [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] 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] А [/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]\triangleleft[/math]