1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Основное определение==
{{Определение|definition=
Рассмотрим граф <tex> G </tex>, возможно c петлями и кратными рёбрами. Определим '''многочлен Татта''' (англ. ''Tutte polynomial'') <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\backslash e} (x, y) </tex> ;
{{Определение|definition=
'''Ранговый многочлен''' (англ. ''(Rank polynomial)'' ) графа <tex> G </tex> есть многочлен от двух переменных, определяемый формулой: <br>
<center><tex dpi = "140"> R_G(u, v) = \sum\limits_{A \subset E} u^{\rho (E) - \rho (A)}v^{|A| - \rho (A)} </tex> </center>
}}
{{Определение
|definition=
Обозначим за <tex> S_n </tex> множество остовных деревьев <tex> T </tex> графа <tex> G </tex>. Будем говорить, что ребро <tex> p \in T</tex> '''внутренне активно''' (англ. ''internally active'') в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash t </tex>, таких что <tex> T \backslash p \cup {q} \in S_n</tex>. Аналогичным образом, будем говорить, что ребро <tex> p \in T</tex> '''внешне активно''' (англ. ''externally active'') в <tex> T </tex>, если <tex> p \prec q </tex> для всех <tex> q \in E \backslash T </tex>, таких что <tex> T \backslash q \cup {p} \in S_n</tex>. Величиной внутренней (внешней) активности будем называть число внутренне (внешне) активных элементов в <tex> T </tex>; эти величины будем обозначать <tex> i(T) </tex> и <tex> e(T) </tex> соответственно.
}}
