97
правок
Изменения
добавлены хроматические многочлены цикла и колеса
'''Примечание:''' Нулевой граф <tex>O_{n}</tex> также можно обозначать <tex>\overline{K_{n}}</tex> (дополнительный граф для полного графа <tex>K_{n}</tex>).
=== Хроматический многочлен цикла ===
Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматичсекий многочлен цикла <tex>P_{С_n} = (x - 1)^n + (-1)^n(x - 1)</tex>
=== Хроматический многочлен колеса ===
{{Определение
|definition=Колесо — это граф с <tex>n</tex> вершинами (<tex>n \le 4</tex>), образованный соединением единственной вершины со всеми вершинами (<tex>n - 1</tex>)-цикла.}}
Пусть <tex>W_n</tex> — колесо с <tex>n</tex> вершинами. Выбрав и зафиксировав один из <tex>x</tex> цветов на вершине, связнной со всеми остальными, имеем <tex> P_{C_{n - 1}}(x - 1) </tex> вариантов раскраски оставшегося графа. Тогда хроматичсекий многочлен колеса <tex>P_{W_n}(x) = x \cdot P_{C_{n - 1}}(x - 1) = x((x - 2)^{(n - 1)} - (-1)^n(x - 2))</tex>.
=== Хроматический многочлен дерева ===
{{Определение
