Материал из Викиконспекты
Хроматический многочлен полного графа
[math]P(K_{n},x)=x(x-1)...(x-n+1)=x^{\underline{n}}[/math], так как первую вершину полного графа [math]K_{n}[/math] можно окрасить в любой из [math]x[/math] цветов, вторую - в любой из оставшихся [math]x-1[/math] цветов и т. д. Очевидно, что если [math]x[/math] меньше [math]n[/math], то и многочлен равен [math]0[/math], потому что один из его множителей [math]0[/math].
Примечание. В некоторых источниках [math]x^{\underline{n}}[/math] ([math]x[/math] в [math]n[/math]-убывающей) обозначают [math]x^{(n)}[/math]. Это не очень удобно, так как легко спутать с [math]n[/math]-ой производной.
Хроматический многочлен пустого графа
[math]P(O_{n},x)=x^{n}[/math], так как каждую из [math]n[/math] вершин нулевого графа [math]O_{n}[/math] можно независимо окрасить в любой из [math]x[/math] цветов.
Примечание. Нулевой граф [math]O_{n}[/math] также можно обозначать [math]\overline{K_{n}}[/math] (дополнительный граф для полного графа [math]K_{n}[/math]).
Хроматический многочлен дерева
| Теорема (хроматический многочлен дерева): |
Граф [math]G[/math] с [math]n[/math] вершинами является деревом тогда и только тогда, когда [math]P(G,x)=x(x-1)^{n-1}[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Сначала покажем, что хроматический многочлен любого дерева [math]T[/math] с [math]n[/math] вершинами есть [math]x(x-1)^{n-1}[/math].
Доказательство индукцией по числу [math]n[/math]. Для [math]n=1[/math] и [math]n=2[/math] результат очевиден. Предположим, что [math]P(T',x)=x(x-1)^{n-2}[/math] для любого дерева [math]T'[/math] с количеством вершин равным [math]n-1[/math]. Пусть [math]uv[/math] - ребро дерева [math]T[/math], такое что [math]v[/math] является висячей вершиной. Хроматический многочлен дерева [math]T[/math] без ребра [math]uv[/math] равен [math]P(T/uv,x)=x(x-1)^{n-2}[/math] по нашему предположению. Вершину [math]v[/math] можно окрасить [math]x-1[/math] способом, так как её цвет должен только лишь отличаться от цвета вершины [math]u[/math]. Итого: [math]P(T,x)=(x-1)P(T/uv,x)=x(x-1)^{n-1}[/math].
Обратно, пусть [math]G[/math] - граф, у которого [math]P(G,x)=x(x-1)^{n-1}[/math]. Тогда верны 2 следующих утверждения:
1. Граф [math]G[/math] связен, потому что если было бы 2 компоненты связности (или больше), то [math]P(G,x)[/math] делился бы на [math]x^2[/math] без остатка.
2. В графе [math]G[/math] количество рёбер равно [math]n-1[/math], так как по теореме о коэффициентах хроматического многочлена, количество рёбер в графе соответствует коэффициенту при [math]x^{n-1}[/math], взятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона:
[math]{P(G,x)=x(x-1)^{n-1}=x(x^{n-1}-\begin{pmatrix}n-1\\1\end{pmatrix}x^{n-2}+\begin{pmatrix}n-1\\2\end{pmatrix}x^{n-3}-...+(-1)^{n-1})=x^{n}-(n-1)x^{n-1}+...+(-1)^{n-1}x}[/math]
Из этих двух утверждений (связность и [math]n-1[/math] ребро) следует, что граф [math]G[/math] является деревом (см. Дерево, эквивалентные определения, теорема, утверждения 1 и 3). |
| [math]\triangleleft[/math] |
Коэффициенты хроматического многочлена
| Теорема: |
Коэффициенты хроматического многочлена составляют знакопеременную последовательность. |
| Доказательство: |
| [math]\triangleright[/math] |
|
… |
| [math]\triangleleft[/math] |
| Теорема: |
Свободный член хроматического многочлена равен [math]0[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
По определению хроматического многочлена для графа [math]G[/math], его значение в точке [math]x[/math] равно количеству способов раскрасить вершины [math]G[/math] правильным образом в [math]x[/math] цветов. Очевидно, что количество способов раскрасить граф в [math]0[/math] цветов равно [math]0[/math]. То есть [math]P(G,0)=0[/math]. Из этого следует, что [math]P(G,x)[/math] кратен [math]x[/math], следовательно его свободный член равен [math]0[/math]. |
| [math]\triangleleft[/math] |
| Теорема: |
Старший коэффициент хроматического многочлена равен [math]1[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Воспользуемся рекуррентной формулой:
[math]P(G,x) = P(G_{1},x) + P(G_{2},x)[/math],
где [math]G_{1}[/math] — граф, полученный из [math]G[/math] добавлением отсутствующего в [math]G[/math] ребра [math]uv[/math], а [math]G_{2}[/math] — граф, полученный из [math]G[/math] отождествлением вершин [math]u[/math] и [math]v[/math] и убиранием вознихших при этом кратных ребер.
Применяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:
[math]P(G,x) = {P(K_{n},x) + a_{1}P(K_{n-1},x) + a_{2}P(K_{n-2},x) + \ldots = x^{\underline{n}} + a_{1}x^{\underline{n-1}}+a_{2}x^{\underline{n-2}}+\ldots}[/math]
Из этой формулы очевидно, что хроматический многочлен имеет старший коэффициент, равный [math]1[/math]. |
| [math]\triangleleft[/math] |
Рекуррентные формулы для хроматических многочленов
См. также
Литература
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
2. Харари Ф. - Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", 2009. - 296 с. ISBN 978-5-397-00622-4
