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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Определение:
Рассмотрим граф [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] с(G) [/math] будем обозначать число компонент связности графа [math] G [/math]. Рангом множества [math] A [/math] будем называть число [math] \rho(A) = |V| - c(G(A)) [/math].


Шаблон:Замечание