Многочлен Татта — различия между версиями
(→Существование и единственность) |
(→Существование и единственность) |
||
Строка 17: | Строка 17: | ||
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | Ранг множества <tex> A </tex> равен количеству рёбер в любом остовном лесе графа <tex> G(A) </tex>. | + | Ранг множества <tex> A </tex> равен количеству рёбер в любом остовном лесе графа <tex> G(A) </tex>. <br>(под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф <tex> G(B) </tex>, что <tex> B \subset A </tex> и <tex> c(G(B)) = c(G(A)) </tex>) |
+ | |proof= | ||
+ | Действительно, в каждой компоненте связности остовного леса рёбер на одно меньше чем вершин, а общее число вершин равно <tex> |V| </tex>. | ||
+ | }} | ||
− | + | Теперь определим сам ранговый многочлен. | |
− | + | ||
− | + | {{Определение|definition= | |
+ | '''Ранговый многочлен''' графа <tex> G </tex> есть многочлен от двух переменных, определяемый формулой: <br> | ||
+ | <center><tex> R_G(u, v) = \sum\limits_{A \subset E} u^{\rho (E) - \rho (A)}v^{|A| - \rho (A)} </tex> | ||
}} | }} |
Версия 16:30, 15 декабря 2013
Основные определения
Определение: |
Рассмотрим граф
| , возможно петлями и кратными рёбрами. Определим многочлен Татта следующими рекурсивными соотношениями:
Разумеется, существование и единственность многочлена Татта ещё нужно доказать. Для того чтобы это сделать, покажем, что многочлену Татта соответствует, так называемый, ранговый многочлен, который уже задаётся явной формулой.
Существование и единственность
Определение: |
Пусть | - некоторый граф. Для множества через будем обозначать граф . Через будем обозначать число компонент связности графа . Рангом множества будем называть число .
Утверждение: |
Ранг множества равен количеству рёбер в любом остовном лесе графа . (под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф , что и ) |
Действительно, в каждой компоненте связности остовного леса рёбер на одно меньше чем вершин, а общее число вершин равно | .
Теперь определим сам ранговый многочлен.
Определение: |
Ранговый многочлен графа </table> |
есть многочлен от двух переменных, определяемый формулой: