Многочлен Татта — различия между версиями
(→Основные определения) |
(→Основные определения) |
||
| Строка 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\e (x, y) </tex>; |
| + | # Если ребро <tex> e </tex> является петлёй, то <tex> T_G (x, y) = yT_G/e (x, y) </tex>; | ||
| + | # Если ребро <tex> e </tex> не является ни мостом, ни петлёй то <tex> T_G (x, y) = T_G\e (x, y) + T_G/e (x, y) </tex>; | ||
| + | }} | ||
| + | |||
| + | Разумеется, существование и единственность многочлена Татта ещё нужно доказать. Для того чтобы это сделать, покажем что многочлену Татта соответствует, так называемый, '''ранговый многочлен''', который уже задаётся явной формулой. | ||
| + | |||
| + | ==Существование и единственность== | ||
| + | {{Определение 123|definition= | ||
| + | Пусть <tex> G = (V,E) </tex> - некоторый граф. Для множества <tex> A \subset E </tex> через <tex> G(A) </tex> будем обозначать граф <tex> (V, A) </tex>. Через <tex> с(G) </tex> будем обозначать '''число компонент связности''' графа <tex> G </tex>. '''Рангом''' множества <tex> A </tex> будем называть число <tex> \rho(A) = |V| - c(G(A)) </tex>. | ||
| + | }} | ||
| + | |||
| + | {{ Замечание|statement= | ||
| + | Ранг множества <tex> А </tex> равен количеству рёбер в любом остовном лесе графа <tex> G(A) </tex>. (Под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф <tex> G(B) </tex>, что <tex> B \subset A </tex> и <tex> c(G(B)) = c(G(A)) </tex>). | ||
| + | |||
}} | }} | ||
Версия 15:59, 15 декабря 2013
Основные определения
| Определение: |
Рассмотрим граф , возможно петлями и кратными рёбрами. Определим многочлен Татта следующими рекурсивными соотношениями:
|
Разумеется, существование и единственность многочлена Татта ещё нужно доказать. Для того чтобы это сделать, покажем что многочлену Татта соответствует, так называемый, ранговый многочлен, который уже задаётся явной формулой.
