Многочлен Татта
Основные определения
Определение: |
Рассмотрим граф
| , возможно петлями и кратными рёбрами. Определим многочлен Татта следующими рекурсивными соотношениями:
Разумеется, существование и единственность многочлена Татта ещё нужно доказать. Для того чтобы это сделать, покажем, что многочлену Татта соответствует, так называемый, ранговый многочлен, который уже задаётся явной формулой.
Существование и единственность
Определение: |
Пусть | - некоторый граф. Для множества через будем обозначать граф . Через будем обозначать число компонент связности графа . Рангом множества будем называть число .
Утверждение: |
Ранг множества равен количеству рёбер в любом остовном лесе графа . (Под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф , что и ). |
Действительно. |