Изменения

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

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

2 байта убрано, 22:59, 22 декабря 2013
Значения многочлена Татта
Заметим, что <tex> \overline {\rho} (A) = 0 </tex> тогда и только тогда, когда <tex> G(A) </tex> не содержит циклов, а <tex> \rho ^*(A) = 0 </tex> тогда и только тогда, когда <tex> G(A) </tex> имеет столько же компонент связности, что и <tex> G </tex>. <br>
Далее, воспользуемся теоремой о связи с ранговым многочленом:
# <tex> T_G(1, 1) = R_G(0, 0) </tex>. Учитывая, что <tex> 0^0 = 1 </tex> и <tex> 0^k = 0 </tex> при <tex> k > 0 </tex>, ненулевыми (а, именно, единичными) будут только те слагаемые, где <tex> \rho^*(A) = 0 </tex> и <tex> \overline {\rho} (A) = 0 </tex>. Это означает, что <tex> G(A) </tex> не содержит циклов и содержит столько же компонент связности, сколько и <tex> G </tex>, то есть является остовным лесом. Суммируя единицы для каждого остовного леса, получаем число остовных лесов.
# <tex> T_G(1, 2) = R_G(0, 1) </tex>. Здесь мы суммируем единицы для тех <tex> A </tex>, где <tex> \rho^*(A) = 0 </tex>, то есть для подграфов имеющих столько же компонент связности, сколько и <tex> G </tex>.
# <tex> T_G(2, 1) = R_G(1, 0) </tex>. Здесь мы суммируем единицы для тех <tex> A </tex>, где <tex> \overline {\rho}(A) = 0 </tex>, то есть для ациклических подграфов.
Анонимный участник

Навигация