Изменения
→Коэффициенты хроматического многочлена
== Коэффициенты хроматического многочлена ==
{{Утверждение
|statement=
Свободный член хроматического многочлена равен <tex>0</tex>.
|proof=
По определению хроматического многочлена для графа <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>.
}}
{{Теорема
|statement=
Старший коэффициент хроматического многочлена равен <tex>1</tex>.
|proof=
Воспользуемся рекуррентной формулой:<br/>
<tex>P(G,x) = P(G_{1},x) + P(G_{2},x)</tex>,<br/>
где <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> и убиранием вознихших при этом кратных ребер.
Применяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть:<br/>
<tex>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}</tex><br/>
Из этой формулы очевидно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.
}}
== Рекуррентные формулы для хроматических многочленов ==
== См. также ==
