editor
177
правок
Изменения
м
→Коэффициенты хроматического многочлена
Свободный член хроматического многочлена равен <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>.
}}
Воспользуемся рекуррентной формулой:<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/>
