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