Изменения

|definition=Пусть дан фиксированный граф <tex>G</tex> и фиксированное число красок <tex>x</tex>. Количество способов правильной <tex>x</tex>-— [[Раскраска графа|раскраски графа ]] <tex>G</tex> называется '''хроматическим многочленом'''(англ. ''chromatic polynomial''). Обозначают Обозначение: <tex>P(G,x)</tex>.

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

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

Граф Пусть <tex>u</tex> и <tex>v</tex> — смежные вершины графа <tex>G</tex> с . Если <tex>nG_1=G\backslash uv</tex> вершинами является деревом тогда и только тогда<tex>G_2=G/uv</tex>, когда то <tex>P(G,x)=P(G_1,x)-P(G_2,x-1)^{n-1}</tex>.

Сначала покажем, что хроматический многочлен любого дерева <tex>T</tex> с <tex>n</tex> вершинами есть <tex>x(x-1)^{n-1}</tex>.<br />Доказательство индукцией по числу <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 /><br />Обратно, пусть <tex>G</tex> - граф, у которого <tex>P(G,x)=x(x-1)^{n-1}</tex>. Тогда верны 2 следующих утверждения:<br />1. Граф <tex>G</tex> связен, потому что если было бы 2 компоненты связности (или больше), то <tex>P(G,x)</tex> делился бы на <tex>x^2</tex> без остатка.<br />2. В графе <tex>G</tex> количество рёбер равно <tex>n-1</tex>, так как по одной Следует из теорем о коэффициентах хроматического многочлена ([[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена]], теорема 4), количество рёбер в графе соответствует коэффициенту при <tex>x^{n-1}</tex>, взятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона:<br /><tex>{P(G,x)=x(x-1)^{n-1}=x\left(x^{n-1}-{n-1 \choose 1}x^{n-2}+{n-1 \choose 2}x^{n-3}-...+(-1)^{n-1}\right)=x^{n}-(n-1)x^{n-1}+...+(-1)^{n-1}x}</tex><br />Из этих двух утверждений (связность и <tex>n-1</tex> ребро) следует, что граф <tex>G</tex> является деревом (см. [[Дерево, эквивалентные определения]], утверждения 1 и 3)предыдущей теоремы.

== Рекуррентные формулы для Примеры хроматических многочленов ===== Хроматический многочлен полного графа ===<tex>P(K_{n},x)=x(x-1)...(x-n+1)=x^{\underline{n}}</tex>, так как первую вершину полного графа <tex>K_{n}</tex> можно окрасить в любой из <tex>x</tex> цветов, вторую — в любой из оставшихся <tex>x-1</tex> цветов и т. д. Очевидно, что если <tex>x</tex> меньше <tex>n</tex>, то и многочлен равен <tex>0</tex>, так как один из его множителей <tex>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>uC_n</tex> и — цикл длины <tex>v</tex> - несмежные вершины графа <tex>Gn</tex>. Если <tex>G_1=G\cup uv</tex>, а <tex>G_2=G/uv</tex> , то Тогда хроматический многочлен цикла <tex>P(GC_n,x)=P(G_1,x- 1)^n +P(G_2,-1)^n(x- 1)</tex>.

Рассмотрим все произвольные раскраски графа Докажем по индукции по количеству вершин.<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>GP(C_k, x) = (x - 1)^k + (-1)^k(x - 1)</tex>. <br>Рассмотрим те из них, при которых вершины случай <tex>un = k + 1</tex> и . По теореме о [[#Рекуррентные_формулы_для_хроматических_многочленов|рекуррентной формуле для хроматических многочленов]]: <tex>vP(C_{k + 1}, x ) = P(C_{k + 1} \setminus e, x) - P(C_{k + 1} / e, x)</tex> окрашены в разные цвета. Если добавить к графу (где <tex>Ge</tex> — любое ребро <tex>uvC_{k + 1}</tex>, то они не изменятся, то есть останутся правильными). Рассмотрим раскраскиЗаметим, при которых что граф <tex>uC_{k + 1} / e</tex> и изоморфен <tex>vC_k</tex> одного цвета. Все эти раскраски останутся правильными и для графа, полученного из а граф <tex>GC_{k + 1} \setminus e</tex> слиянием вершин является [[#Хроматический_многочлен_простой_цепи|простой цепью]].Тогда <tex>uP(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>v(x-1)^{k+1}+(-1)^{k+1}(x-1)</tex>.

'''Следствие:'''=== Хроматический многочлен любого графа колеса ===Пусть <tex>W_n</tex> — [[Двойственный_граф_планарного_графа|колесо]] с <tex>n</tex> вершинами. Выбрав и зафиксировав один из <tex>Gx</tex> равен сумме хроматических многочленов некоторого числа полных графовцветов на вершине, число вершин в которых не большесвязнной со всеми остальными, чем в графе имеем <tex> P(C_{n - 1}, x - 1) </tex> вариантов раскраски оставшегося графа. Тогда хроматический многочлен колеса <tex>GP_{W_n}(x) = x \cdot P_{C_{n - 1}}(x - 1) = x((x - 2)^{(n - 1)} + (-1)^{(n - 1)}(x - 2))</tex>.

Пусть <tex>u</tex> и <tex>v</tex> - смежные вершины графа Граф <tex>G</tex>. Если с <tex>G_1=G\backslash uvn</tex> вершинами является деревом тогда и <tex>G_2=G/uv</tex>только тогда, то когда <tex>P(G,x)=Px(G_1,x-1)^{n-P(G_2,x)1}</tex>.

Следует <tex>\Rightarrow</tex><br>Сначала покажем, что хроматический многочлен любого дерева <tex>T</tex> с <tex>n</tex> вершинами есть <tex>x(x-1)^{n-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>Обратно, пусть <tex>G</tex> — граф, у которого <tex>P(G,x)=x(x-1)^{n-1}</tex>. Тогда верны два следующих утверждения:<ol> <li>Граф <tex>G</tex> связен, потому что если было бы две компоненты связности (или больше), то <tex>P(G,x)</tex> делился бы на <tex>x^2</tex> без остатка.<br /></li> <li>В графе <tex>G</tex> количество рёбер равно <tex>n-1</tex>, так как по одной из предыдущей теоремытеорем о коэффициентах хроматического многочлена ([[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена]], теорема 4), количество рёбер в графе соответствует коэффициенту при <tex>x^{n-1}</tex>, взятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона:<br /><tex>{P(G,x)=x(x-1)^{n-1}=x\left(x^{n-1}-{n-1 \choose 1}x^{n-2}+{n-1 \choose 2}x^{n-3}-...+(-1)^{n-1}\right)=x^{n}-(n-1)x^{n-1}+...+(-1)^{n-1}x}</tex><br /> </li></ol>Из этих двух утверждений (связность и <tex>n-1</tex> ребро) следует, что граф <tex>G</tex> является деревом (см. [[Дерево, эквивалентные определения]], утверждения 1 и 3).

где <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/>

== См. также ==== Литература Источники информации ==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 {{---}} Хроматический многочлен]]