Изменения
→Значение многочлена Татта для некоторых значений переменных
}}
==Значение многочлена Татта =={{Теорема|statement=Для любого графа <tex> G </tex> верно, что:# <tex> T_G (1, 1) </tex> равно количеству остовных лесов;# <tex> T_G (1, 2) </tex> равно количеству подграфов <tex> G </tex>, имеющих столько же компонент связности, что и <tex> G </tex>;# <tex> T_G (2, 1) </tex> равно количеству ациклических подграфов <tex> G </tex>.|proof=Заметим, что <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>, то есть для ациклических подграфов. }}
