Изменения
→Основные определения
Рассмотрим граф <tex> G </tex>, возможно петлями и кратными рёбрами. Определим '''многочлен Татта''' <tex> T_G (x, y) </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>).
}}
