Многочлен Татта — различия между версиями
(→Основные определения) |
(→Основные определения) |
||
Строка 4: | Строка 4: | ||
# Если граф <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_{G\backslash e} (x, y) </tex> ; | # Если ребро <tex> e </tex> является мостом, то <tex> T_G (x, y) = xT_{G\backslash e} (x, y) </tex> ; | ||
− | # Если ребро <tex> e </tex> является петлей, то <tex> T_G (x, y) = | + | # Если ребро <tex> e </tex> является петлей, то <tex> T_G (x, y) = yT_{G/e} (x, y) </tex>; |
− | # Если ребро <tex> e </tex> не является ни мостом, ни петлей то <tex> T_G (x, y) = | + | # Если ребро <tex> e </tex> не является ни мостом, ни петлей то <tex> T_G (x, y) = T_{G\backslash e} (x, y) + T_{G/e} (x, y) </tex>; |
}} | }} | ||
Версия 16:06, 15 декабря 2013
Основные определения
Определение: |
Рассмотрим граф
| , возможно петлями и кратными рёбрами. Определим многочлен Татта следующими рекурсивными соотношениями:
Разумеется, существование и единственность многочлена Татта ещё нужно доказать. Для того чтобы это сделать, покажем что многочлену Татта соответствует, так называемый, ранговый многочлен, который уже задаётся явной формулой.