Материал из Викиконспекты
Основные определения
| Определение: |
Рассмотрим граф [math] G [/math], возможно петлями и кратными рёбрами. Определим многочлен Татта [math] T_G (x, y) [/math] следующими рекурсивными соотношениями:
- Если граф [math] G [/math] пуст, то [math] T_G (x, y) = 1 [/math];
- Если ребро [math] e [/math] является мостом, то [math] T_G (x, y) = xT_G\backslash _e (x, y) [/math] ;
- Если ребро [math] e [/math] является петлей, то [math] T_G (x, y) = yT_G/_e (x, y) [/math];
- Если ребро [math] e [/math] не является ни мостом, ни петлей то [math] T_G (x, y) = T_G\backslash _e (x, y) + T_G/_e (x, y) [/math];
|
Разумеется, существование и единственность многочлена Татта ещё нужно доказать. Для того чтобы это сделать, покажем что многочлену Татта соответствует, так называемый, ранговый многочлен, который уже задаётся явной формулой.
Существование и единственность
