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