Изменения

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

Хроматический многочлен

2 байта добавлено, 18:25, 5 июля 2018
Хроматический многочлен цикла
'''База индукции''': рассмотрим случай <tex>n = 3</tex>: <tex>P(C_3, x) = x(x - 1)(x - 2) = (x^3 - 3x^2 + 3x - 1) - (x - 1) = (x - 1)^3 + (-1)^3(x - 1)</tex>, что удовлетворяет формулировке теоремы.<br>
'''Индукционный переход''': пусть <tex>P(C_k, x) = (x - 1)^k + (-1)^k(x - 1)</tex>.<br>
Рассмотрим случай <tex>n = k + 1</tex>. По теореме о [[#Рекуррентные_формулы_для_хроматических_многочленов|рекурентной рекуррентной формуле для хроматических многочленов]]: <tex>P(C_{k + 1}, x ) = P(C_{k + 1} \setminus e, x) - P(C_{k + 1} / e, x)</tex> (где <tex>e</tex> — любое ребро <tex>C_{k + 1}</tex>).
Заметим, что граф <tex>C_{k + 1} / e</tex> изоморфен <tex>C_k</tex>, а граф <tex>C_{k + 1} \setminus e</tex> является [[#Хроматический_многочлен_простой_цепи|простой цепью]].
Тогда <tex>P(C_{k + 1}, x)=P(T_{k + 1}, x)-P(C_k, x)=x(x-1)^k-(x-1)^k-(-1)^k(x-1)=</tex> <tex>(x-1)^{k+1}+(-1)^{k+1}(x-1)</tex>.
560
правок

Навигация