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

Материал из Викиконспекты
Версия от 15:59, 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\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\e (x, y) + T_G/e (x, y) [/math];


Разумеется, существование и единственность многочлена Татта ещё нужно доказать. Для того чтобы это сделать, покажем что многочлену Татта соответствует, так называемый, ранговый многочлен, который уже задаётся явной формулой.

Существование и единственность

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

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