81
правка
Изменения
→Рекуррентные формулы для хроматических многочленов
== Рекуррентные формулы для хроматических многочленов ==
Граф <tex>G/uv</tex> — граф, полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>, то есть у которого вершины <tex>u</tex> и <tex>v</tex> будут отождествлены и при этом будут отброшены все петли и кратность ребер будет сведена к единице.
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> - несмежные вершины графа <tex>G</tex>. Если <tex>G_1=G\cup uv</tex>, а <tex>G_2=G/uv</tex> (стягивание ребра) , то <tex>P(G,x)=P(G_1,x)+P(G_2,x)</tex>.
|proof=
Рассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, при которых вершины <tex>u</tex> и <tex>v</tex> окрашены в разные цвета. Если добавить к графу <tex>G</tex> ребро <tex>uv</tex>, то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых <tex>u</tex> и <tex>v</tex> одного цвета. Все эти раскраски останутся правильными и для графа, полученного из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>.
}}
