97
правок
Изменения
м
Будем обозначать за <tex>G/uv</tex> граф, полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>, то есть у которого вершины <tex>u</tex> и <tex>v</tex> будут отождествлены и при этом будут отброшены все петли и кратность ребер будет сведена к единице.
стягивание ребра вынесено перед теоремой о хроматическом многочлене дереве
}}
== Примеры хроматических многочленов ===== Хроматический многочлен полного графа ===
<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 />
=== Хроматический многочлен нуль-графа ===
{{Определение
|definition='''Нуль-граф''' (пустой граф, вполне несвязный граф, null graph, empty graph, edgeless graph) — регулярный граф степени 0, т.е. граф без рёбер.}}
'''Примечание:''' Нулевой граф <tex>O_{n}</tex> также можно обозначать <tex>\overline{K_{n}}</tex> (дополнительный граф для полного графа <tex>K_{n}</tex>).
=== Хроматический многочлен дерева ==={{Определение|definition='''Стягивание ребра''' — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>G/uv</tex> граф, полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>.}}
{{Теорема
|about=
== Рекуррентные формулы для хроматических многочленов ==
{{Теорема
|statement=
