Изменения

|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(K_{n}G,x)=xP(G_1,x-1)...+P(G_2,x-n+1)</tex>.|proof=x^{\underline{n}}Рассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, так как первую вершину полного графа при которых вершины <tex>u</tex> и <tex>K_{n}v</tex> можно окрасить окрашены в любой из разные цвета. Если добавить к графу <tex>G</tex> ребро <tex>xuv</tex> цветов, вторую - в любой из оставшихся то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых <tex>x-1u</tex> цветов и т<tex>v</tex> одного цвета. д. ОчевидноВсе эти раскраски останутся правильными и для графа, что если полученного из <tex>G</tex> слиянием вершин <tex>xu</tex> меньше и <tex>nv</tex>.}}'''Замечание:'''Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то и на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.  '''Следствие:'''Хроматический многочлен равен любого графа <tex>0G</tex>равен сумме хроматических многочленов некоторого числа полных графов, число вершин в которых не больше, потому что один из его множителей чем в графе <tex>0G</tex>. {{Теорема|statement=Пусть <tex>u<br /tex>Примечание. В некоторых источниках и <tex>x^{\underline{n}}v</tex> (— смежные вершины графа <tex>xG</tex> в . Если <tex>nG_1=G\backslash uv</tex>-убывающей) обозначают и <tex>x^{(n)}G_2=G/uv</tex>. Это не очень удобно, так как легко спутать с то <tex>nP(G,x)=P(G_1,x)-P(G_2,x)</tex>-ой производной.|proof=Следует из предыдущей теоремы.}}

== Примеры хроматических многочленов ===== Хроматический многочлен пустого полного графа ===<tex>P(O_K_{n},x)=x(x-1)...(x-n+1)=x^{\underline{n}}</tex>, так как каждую из первую вершину полного графа <tex>K_{n}</tex> вершин нулевого графа можно окрасить в любой из <tex>O_{n}x</tex> можно независимо окрасить цветов, вторую — в любой из оставшихся <tex>x-1</tex> цветови т. д.Очевидно, что если <tex>x<br /tex>Примечание. Нулевой граф меньше <tex>O_{n}</tex> также можно обозначать , то и многочлен равен <tex>\overline{K_{n}}0</tex> (дополнительный граф для полного графа , так как один из его множителей <tex>K_{n}0</tex>).

=== Хроматический многочлен дерева нуль-графа ==={{Определение|definition='''Нуль-граф''' (пустой граф, вполне несвязный граф; англ. ''null graph'', ''empty graph'', ''edgeless graph'') — регулярный граф степени <tex>0</tex>, т.е. граф без рёбер.}}<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> — простая цепь, состоящая из <tex>n</tex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из <tex>x</tex> цветов, вторую и последующие в один из <tex>x - 1</tex> цветов (т.е. так, чтобы цвет не совпадал с предыдущей вершиной). Тогда <tex>P(T_n, x) = x(x - 1) ^ {n - 1}</tex>. === Хроматический многочлен цикла ===

хроматический многочлен деревацикла

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

Сначала покажем, что хроматический многочлен любого дерева <tex>T</tex> с <tex>n</tex> вершинами есть <tex>x(x-1)^{n-1}</tex>Докажем по индукции по количеству вершин.<br />Доказательство индукцией по числу <tex>n</tex>. Для '''База индукции''': рассмотрим случай <tex>n=13</tex> и <tex>n=2</tex> результат очевиден. Предположим, что : <tex>P(T'C_3,x)=x(x-1)(x - 2) = (x^{n3 -3x^2}</tex> для любого дерева <tex>T'</tex> с количеством вершин равным <tex>n+ 3x -1</tex>. Пусть <tex>uv</tex> ) - ребро дерева <tex>T</tex>, такое что <tex>v</tex> является висячей вершиной. Хроматический многочлен дерева <tex>T</tex> без ребра <tex>uv</tex> равен <tex>P(T/uv,x- 1)=x(x-1)^{n3 + (-2}</tex> по нашему предположению. Вершину <tex>v</tex> можно окрасить <tex>1)^3(x-1)</tex> способом, так как её цвет должен только лишь отличаться от цвета вершины что удовлетворяет формулировке теоремы.<texbr>u</tex>. Итого'''Индукционный переход''': пусть <tex>P(TC_k,x)=(x-1)P^k + (T/uv,x-1)=x^k(x-1)^{n-1}</tex>.<br /><br />Обратно, пусть Рассмотрим случай <tex>Gn = k + 1</tex> - граф, у которого . По теореме о [[#Рекуррентные_формулы_для_хроматических_многочленов|рекуррентной формуле для хроматических многочленов]]: <tex>P(GC_{k + 1},x)=xP(C_{k + 1} \setminus e, x) -1)^P(C_{n-k + 1}</tex>. Тогда верны 2 следующих утверждения:<br />1. Граф <tex>Ge, x)</tex> связен, потому что если было бы 2 компоненты связности (или больше), то где <tex>P(G,x)e</tex> делился бы на — любое ребро <tex>x^2C_{k + 1}</tex> без остатка).<br />2. В графе Заметим, что граф <tex>GC_{k + 1} / e</tex> количество рёбер равно изоморфен <tex>n-1C_k</tex>, так как по теореме о коэффициентах хроматического многочлена, количество рёбер в графе соответствует коэффициенту при а граф <tex>x^C_{n-k + 1}\setminus e</tex>, взятому со знаком минусявляется [[#Хроматический_многочлен_простой_цепи|простой цепью]]. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона:<br />Тогда <tex>{P(GC_{k + 1},x)=P(T_{k + 1}, x)-P(C_k, x-1)^{n-1}=x(x^{n-1})^k-\begin{pmatrix}n-1\\1\end{pmatrix}(x^{n-2}+\begin{pmatrix}n-1\\2\end{pmatrix}x)^{n-3}k-...+(-1)^{nk(x-1})=</tex> <tex>(x^{n}-(n-1)x^{n-k+1}+...+(-1)^{n-k+1}(x}</tex><br />Из этих двух утверждений (связность и <tex>n-1</tex> ребро) следует, что граф <tex>G</tex> является деревом (см. [[Дерево, эквивалентные определения]], теорема, утверждения 1 и 3).

 == Рекуррентные формулы для хроматических многочленов = Хроматический многочлен колеса ===Пусть <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>. ===Хроматический многочлен дерева = Коэффициенты хроматического многочлена ==

Коэффициенты хроматического многочлена составляют знакопеременную последовательностьГраф <tex>G</tex> с <tex>n</tex> вершинами является деревом тогда и только тогда, когда <tex>P(G,x)=x(x-1)^{n-1}</tex>.

По определению хроматического многочлена для графа <tex>G</tex>, его значение в точке <tex>x</tex> равно количеству способов раскрасить вершины <tex>G</tex> правильным образом в <tex>x</tex> цветов. Очевидно, что количество Количество способов раскрасить граф в <tex>0</tex> цветов равно <tex>0</tex>. То есть <tex>P(G,0)=0</tex>. Из этого следует, что <tex>P(G,x)</tex> кратен <tex>x</tex>, следовательно его свободный член равен <tex>0</tex>.

где <tex>G_{1}</tex> — граф, полученный из <tex>G</tex> добавлением отсутствующего в <tex>G</tex> ребра <tex>uv</tex>, а <tex>G_{2}</tex> — граф, полученный из <tex>G</tex> отождествлением слиянием вершин <tex>u</tex> и <tex>v</tex> в одну и убиранием вознихших удалением возникших при этом кратных ребер.

Из этой формулы очевидновидно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.}} {{Теорема|about=3|statement=Коэффициенты хроматического многочлена составляют знакопеременную последовательность.|proof=Индукция по количеству вершин.<br/>'''База индукции:'''<br/>Теорема верна для графа <tex>G</tex> из одной вершины, потому что <tex>P(G,x)=x</tex>.<br/>'''Индукционный переход''' (<tex>n \to n+1)</tex>:<br/>Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на <tex>n+1</tex> вершине.Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, то есть <tex>G</tex> является <tex>O_{n+1}</tex>, то его хроматический многочлен <tex>P(G,x)=x^{n+1}</tex> обладает доказываемым свойством. Теперь предположим, что для всех <tex>(n+1,m)</tex>-графов теорема верна. Возьмем <tex>(n+1,m+1)</tex>-граф <tex>G_{1}</tex> и его ребро <tex>uv</tex>. Обозначим за <tex>G</tex> граф, полученный из <tex>G_{1}</tex> удалением ребра <tex>uv</tex> (<tex>G=G_{1}-uv</tex>), а за <tex>G_{2}</tex> — граф, полученный из <tex>G_{1}</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>. Тогда из рекуррентной формулы следует:<br/><tex>P(G_{1},x)=P(G,x)-P(G_{2},x)</tex>.Так как <tex>G</tex> — <tex>(n+1,m)</tex>-граф, а в <tex>G_{2}</tex> — <tex>n</tex> вершин, то для <tex>G</tex> и <tex>G_{2}</tex> теорема верна:<br/><tex>{P(G,x)=x^{n+1}-a_{1}x^{n}+a_{2}x^{n-1}-a_{3}x^{n-2}+\ldots}</tex> ,<br/><tex>{P(G_{2},x)=x^{n}-b_{1}x^{n-1}+b_{2}x^{n-2}+\ldots}</tex> ,<br/>где <tex>a_{1}</tex>, <tex>a_{2}</tex> … <tex>a_{n+1}</tex>, <tex>b_{1}</tex>, <tex>b_{2}</tex> … <tex>b_{n}</tex> — некоторые неотрицательные целые числа. Из этих равенств получаем:<br/><tex>P(G_{1},x)=x^{n+1}-(a_{1}+1)x^{n}+(a_{2}+b_{1})x^{n-1}+\ldots</tex>.Видно, что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность.}} {{Теорема|about=4|statement=Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.|proof=Из доказательства '''Теоремы (3)''' видно, что при увеличении количества ребер графа на <tex>1</tex>, второй коэффициент также увеличивается на <tex>1</tex>. Так как для пустого графа второй коэффициент равен <tex>0</tex>, то утверждение верно для любого графа.

== См. также ==== Литература Источники информации ==1. * Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). '''ISBN 978-5-8114-1068-2'''<br />2. * Харари Ф. - — Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", 2009. - 296 с. '''ISBN 978-5-397-00622-4'''* [[wikipedia:en:Chromatic_polynomial| Wikipedia {{---}} Chromatic polynomial]]* [[wikipedia:ru:Хроматическое_число#Хроматический_многочлен| Wikipedia {{---}} Хроматический многочлен]]