Изменения

Перейти к: навигация, поиск

Многочлен Татта

1 байт убрано, 15:09, 16 декабря 2013
Существование и единственность
Если граф <tex> G </tex> пуст, то единственным подмножеством <tex> E </tex> является пустое множество, для которого нет важных и лишних рёбер. Поэтому <tex> \rho^*(\emptyset ) = \overline {\rho} (\emptyset) = 0 </tex> и <tex> R_G(u, v) = 1 = T_G(u + 1, v + 1) </tex>.<br>
Пусть граф <tex> G </tex> не пуст. Докажем, что для рангового многочлена выполняются соотношения Татта (из определения многочлена Татта). Выберем некоторое ребро <tex> e \in E </tex> и разобьём все подмножества <tex> E </tex> на пары вида <tex> (A, A') </tex>, где <tex> e \not\in A </tex> и <tex> A' = A \cup {e} </tex>. Тогда <br><center><tex dpi = "130">
R_G(u, v) = \sum\limits_{A \subset {E \backslash {e}}} ( u^{\rho^* (A)}v^{\overline {\rho }(A)}} + u^{\rho^* (A')}v^{\overline {\rho } (A')}} )
</tex></center>
}}
Анонимный участник

Навигация