Многочлен Татта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Рассмотрим граф <tex> G </tex>, возможно петлями и кратными рёбрами. Определим '''многочлен Татта''' <tex> T_G (x, y) </tex> следующими рекурсивными соотношениями:
 
Рассмотрим граф <tex> G </tex>, возможно петлями и кратными рёбрами. Определим '''многочлен Татта''' <tex> T_G (x, y) </tex> следующими рекурсивными соотношениями:
 
# Если граф <tex> G </tex> пуст, то <tex> T_G (x, y) = 1 </tex>;
 
# Если граф <tex> G </tex> пуст, то <tex> T_G (x, y) = 1 </tex>;
# Если ребро <tex> e </tex> является мостом, то <tex> T_G (x, y) = xT_Ge (x, y) </tex> ;
+
# Если ребро <tex> e </tex> является мостом, то <tex> T_G (x, y) = xT_G\e (x, y) </tex> ;
 
# Если ребро <tex> e </tex> является петлей, то <tex> T_G (x, y) = yT_G/e (x, y) </tex>;
 
# Если ребро <tex> e </tex> является петлей, то <tex> T_G (x, y) = yT_G/e (x, y) </tex>;
 
# Если ребро <tex> e </tex> не является ни мостом, ни петлей то <tex> T_G (x, y) = T_G\e (x, y) + T_G/e (x, y) </tex>;
 
# Если ребро <tex> e </tex> не является ни мостом, ни петлей то <tex> T_G (x, y) = T_G\e (x, y) + T_G/e (x, y) </tex>;

Версия 16:02, 15 декабря 2013

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

Определение:
Рассмотрим граф [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

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