Изменения

|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>.}}

|definition='''Нуль-граф''' (пустой граф, вполне несвязный граф, ; англ. ''null graph'', ''empty graph'', ''edgeless graph'') — регулярный граф степени <tex>0</tex>, т.е. граф без рёбер.}}

Пусть <tex>T_n</tex> - — простая цепь, состоящая из <tex>n </tex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из <tex>x</tex> цветов, вторую и последующие в один из <tex>x - 1</tex> цветов (т.е. так, чтобы цвет не совпадал с предыдущей вершиной). Тогда <tex>P_{P(T_n}(, x) = x(x - 1) ^ {n - 1}</tex>.

Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий многочлен цикла <tex>P_{P(C_n}(, x) = (x - 1)^n + (-1)^n(x - 1)</tex>.

Рассмотрим случай <tex>n = 3</tex>: <tex>P_{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_{P(С_k} , x) = (x - 1)^k + (-1)^k(x - 1)</tex>. <br>Рассмотрим случай <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_{ P(C_{k + 1} } , x ) = P_{ P(C_{k + 1} \setminus e } , x) - P_{ P(C_{k + 1} / e }, x)</tex> (где <tex>e</tex> - — любое ребро <tex>C_{k + 1}</tex>).

Тогда <tex>P_{ P(C_{k + 1} }(, x)=P_{ P(T_{k + 1} }(, x)-P_{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>n</tex>. Для <tex>n=1</tex> и <tex>n=2</tex> результат очевиден. Предположим, что <tex>P(T',x)=x(x-1)^{n-2}</tex> для любого дерева <tex>T'</tex> с количеством вершин равным <tex>n-1</tex>. Пусть <tex>uv</tex> — ребро дерева <tex>T</tex>, такое что <tex>v</tex> является висячей вершиной. Хроматический многочлен дерева <tex>T</tex> без ребра <tex>uv</tex> равен <tex>P(T/uv,x)=x(x-1)^{n-2}</tex> по нашему предположению. Вершину <tex>v</tex> можно окрасить <tex>x-1</tex> способом, так как её цвет должен только лишь отличаться от цвета вершины <tex>u</tex>. Итого: <tex>P(T,x)=(x-1)P(T/uv,x)=x(x-1)^{n-1}</tex>.<br><tex>\Leftarrow</tex><br>

== Литература Источники информации ==