81
правка
Изменения
Нет описания правки
== Хроматический многочлен полного графа ==
<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>.<br />
Примечание. В некоторых источниках <tex>x^{\underline{n}}</tex> (<tex>x</tex> в <tex>n</tex>-убывающей) обозначают <tex>x^{(n)}</tex>. Это не очень удобно, так как легко спутать с <tex>n</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>, так как по одной из теорем о коэффициентах хроматического многочлена ([[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена]], теорема 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 />
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> - — смежные вершины графа <tex>G</tex>. Если <tex>G_1=G\backslash uv</tex> и <tex>G_2=G/uv</tex>, то <tex>P(G,x)=P(G_1,x)-P(G_2,x)</tex>.
|proof=
Следует из предыдущей теоремы.
