97
правок
Изменения
хроматический многочлен цикла
{{Определение
|definition=Пусть дан фиксированный граф <tex>G</tex> и фиксированное число красок <tex>x</tex>. Количество способов правильной <tex>x</tex> — [[Раскраска графа|раскраски графа]] <tex>G</tex> называется '''хроматическим многочленом''' ('''chromatic polynomial'''). Обозначение: <tex>P(G,x)</tex>.
}}
== Рекуррентные формулы для хроматических многочленов ==
{{Определение
|definition='''Стягивание ребра''' (edge contraction) — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>G/uv</tex> граф, полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>.}}
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> - несмежные вершины графа <tex>G</tex>. Если <tex>G_1=G\cup uv</tex>, а <tex>G_2=G/uv</tex>, то <tex>P(G,x)=P(G_1,x)+P(G_2,x)</tex>.
|proof=
Рассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, при которых вершины <tex>u</tex> и <tex>v</tex> окрашены в разные цвета. Если добавить к графу <tex>G</tex> ребро <tex>uv</tex>, то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых <tex>u</tex> и <tex>v</tex> одного цвета. Все эти раскраски останутся правильными и для графа, полученного из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>.
}}
'''Замечание:'''
Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.
'''Следствие:'''
Хроматический многочлен любого графа <tex>G</tex> равен сумме хроматических многочленов некоторого числа полных графов, число вершин в которых не больше, чем в графе <tex>G</tex>.
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> — смежные вершины графа <tex>G</tex>. Если <tex>G_1=G\backslash uv</tex> и <tex>G_2=G/uv</tex>, то <tex>P(G,x)=P(G_1,x)-P(G_2,x)</tex>.
|proof=
Следует из предыдущей теоремы.
}}
<tex>P(O_{n},x)=x^{n}</tex>, так как каждую из <tex>n</tex> вершин нулевого графа <tex>O_{n}</tex> можно независимо окрасить в любой из <tex>x</tex> цветов.<br>
'''Примечание:''' Нулевой граф <tex>O_{n}</tex> также можно обозначать <tex>\overline{K_{n}}</tex> (дополнительный граф для полного графа <tex>K_{n}</tex>).
=== Хроматический многочлен простой цепи ===
Пусть <tex>T_n</tex> - простая цепь, состоящая из n вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из <tex>x</tex> цветов, вторую и последующие в один из <tex>x - 1</tex> цветов (т.е. так, чтобы цвет не совпадал с предыдущей вершиной). Тогда <tex>P_{T_n}(x) = x(x - 1) ^ {n - 1}</tex>.
=== Хроматический многочлен цикла ===
{{Теорема|about=хроматический многочлен цикла|statement=Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий многочлен цикла <tex>P_{C_n}(x) = (x - 1)^n + (-1)^n(x - 1)</tex>.|proof=Рассмотрим случай <tex>n = 3</tex>: <tex>P_{C_3}(x) = x(x - 1)(x - 2) = (x - 1)(x^2 - x) = (x - 1)^3 + (-1)^3(x - 1)</tex>, что удовлетворяет формулировке теоремы.<br>Пусть <tex>P_{С_k} = (x - 1)^k + (-1)^k(x - 1)</tex>. Рассмотрим случай <tex>n = k + 1</tex>. По теореме о [[#.D0.A0.D0.B5.D0.BA.D1.83.D1.80.D1.80.D0.B5.D0.BD.D1.82.D0.BD.D1.8B.D0.B5_.D1.84.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D1.8B_.D0.B4.D0.BB.D1.8F_.D1.85.D1.80.D0.BE.D0.BC.D0.B0.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D1.85_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D1.87.D0.BB.D0.B5.D0.BD.D0.BE.D0.B2|рекурентной формуле для хроматических сногочленовмногочленов]]: <tex>P_{ C_{k + 1} } = P_{ C_{k + 1} \setminus e } - P_{ C_{k + 1} / e }</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> является [[#.D0.A5.D1.80.D0.BE.D0.BC.D0.B0.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D0.B9_.D0.BC.D0.BD.D0.BE.D0.B3.D0.BE.D1.87.D0.BB.D0.B5.D0.BD_.D0.BF.D1.80.D0.BE.D1.81.D1.82.D0.BE.D0.B9_.D1.86.D0.B5.D0.BF.D0.B8|простой цепью]] .Тогда хроматичсекий многочлен цикла <tex>P_{С_nC_{k + 1} }(x)=P_{ T_{k + 1} }(x)-P_{C_k} (x)= x(x - 1)^n k-(x-1)^k-(-1)^k(x-1)=</tex><tex>(x-1)^{k+1}+ (-1)^n{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(x - 2))</tex>.
=== Хроматический многочлен дерева ===
{{Теорема
|about=
</ol>
Из этих двух утверждений (связность и <tex>n-1</tex> ребро) следует, что граф <tex>G</tex> является деревом (см. [[Дерево, эквивалентные определения]], утверждения 1 и 3).
}}
