Изменения

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

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

8 байт убрано, 02:38, 26 декабря 2020
м
Хроматический многочлен колеса: Исправил ошибку в формуле
хроматический многочлен цикла
|statement=
Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий хроматический многочлен цикла <tex>P(C_n, x) = (x - 1)^n + (-1)^n(x - 1)</tex>.
|proof=
Докажем по индукции по количеству вершин.<br>
'''База индукции''': рассмотрим случай <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>.
}}
 
=== Хроматический многочлен колеса ===
Пусть <tex>W_n</tex> — [[Двойственный_граф_планарного_графа|колесо]] с <tex>n</tex> вершинами. Выбрав и зафиксировав один из <tex>x</tex> цветов на вершине, связнной со всеми остальными, имеем <tex> P(C_{n - 1}, x - 1) </tex> вариантов раскраски оставшегося графа. Тогда хроматичсекий хроматический многочлен колеса <tex>P_{W_n}(x) = x \cdot P_{C_{n - 1}}(x - 1) = x((x - 2)^{(n - 1)} - + (-1)^{(n- 1)}(x - 2))</tex>. 
=== Хроматический многочлен дерева ===
{{Теорема
1
правка

Навигация