81
правка
Изменения
Нет описания правки
{{Определение
|definition=Пусть дан фиксированный граф <tex>G</tex> и фиксированное число красок <tex>x</tex>. Количество способов правильной <tex>x</tex>-раскраски графа <tex>G</tex> называется '''хроматическим многочленом'''. Обозначают <tex>P(G,x)</tex>.
}}
== Операция стягивания ребра ==
{{Определение
|definition=Пусть <tex>uv</tex> — ребро графа <tex>G</tex>, не являющееся петлёй. Тогда графом <tex>G/uv</tex> назовём граф, у которого вершины <tex>u</tex> и <tex>v</tex> будут отождествлены, при этом будут отброшены все петли и кратность ребер будет сведена к единице. Граф <tex>G/uv</tex> получен из графа <tex>G</tex> '''стягиванием ребра <tex>uv</tex>'''
}}
