Изменения
→Коэффициенты хроматического многочлена
== Коэффициенты хроматического многочлена ==
{{Теорема
|statementabout=Коэффициенты хроматического многочлена составляют знакопеременную последовательность.|proof=…}} {{Теорема1
|statement=
Свободный член хроматического многочлена равен <tex>0</tex>.
{{Теорема
|about=
2
|statement=
Старший коэффициент хроматического многочлена равен <tex>1</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/>
Из этой формулы очевидно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.
}}
{{Теорема
|about=
3
|statement=
Коэффициенты хроматического многочлена составляют знакопеременную последовательность.
|proof=
Индукция по количеству ребер.<br/>
'''База индукции:'''<br/>
Теорема очевидна для графа <tex>G</tex> из одной вершины, потому что <tex>P(G,x)=x</tex>.<br/>
'''Индукционный переход''' (<tex>n \to n+1)</tex>:<br/>
Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на <tex>n+1</tex> вершинах.
Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, то есть <tex>G</tex> является <tex>O_{n+1}</tex>, то его хроматический многочлен <tex>P(G,x)=x^{n+1}</tex> удовлетворяет доказываемому свойству. Теперь предположим, что для всех <tex>(n+1,m)</tex>-графов теорема верна. Возьмем <tex>(n+1,m+1)</tex>-граф <tex>G_{1}</tex> и его ребро <tex>uv</tex>. Обозначим за <tex>G</tex> граф, полученный из <tex>G_{1}</tex> удалением ребра <tex>uv</tex> (<tex>G=G_{1}-uv</tex>), а за <tex>G_{2}</tex> — граф, полученный из <tex>G_{1}</tex> «слитием» вершин <tex>u</tex> и <tex>v</tex>. Тогда из рекуррентной формулы следует:<br/>
<tex>P(G_{1},x)=P(G,x)-P(G_{2},x)</tex>.
Так как <tex>G</tex> — <tex>(n+1,m)</tex>-граф, а в <tex>G_{2}</tex> — <tex>n</tex> вершин, то для <tex>G</tex> и <tex>G_{2}</tex> теорема верна:<br/>
<tex>{P(G,x)=x^{n+1}-a_{1}x^{n}+a_{2}x^{n-1}-a_{3}x^{n-2}+\ldots}</tex> ,<br/>
<tex>{P(G_{2},x)=x^{n}-b_{1}x^{n-1}+b_{2}x^{n-2}+\ldots}</tex> ,<br/>
где <tex>a_{1}</tex>, <tex>a_{2}</tex>, …, <tex>a_{n+1}</tex>, <tex>b_{1}</tex>, <tex>b_{2}</tex>, …, <tex>b_{n}</tex> — некоторые неотрицательные целые числа. Из этих равенств получаем:<br/>
<tex>P(G_{1},x)=x^{n+1}-(a_{1}+1)x^{n}+(a_{2}+b_{1})x^{n-1}+\ldots</tex>.
Видно, что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность, что и требовалось доказать.
}}
{{Теорема
|about=
4
|statement=
Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.
|proof=
Из доказательства '''Теоремы (3)''' видно, что при увеличении количества ребер графа на <tex>1</tex>, второй коэффициент также увеличивается на <tex>1</tex>. Так как для пустого графа второй коэффициент равен <tex>0</tex>, то утверждение верно для любого графа.
}}
== См. также ==
== Литература ==
