68
правок
Изменения
Нет описания правки
Следовательно, перебрав все возможные разбиения на <tex>i</tex> независимых множеств, получим, что число интересующих нас раскрасок графа <tex>G</tex> равно <tex>pt(G,i) \cdot x \cdot (x - 1) \cdot \ldots \cdot (x - i + 1) = pt(G,i) \cdot x^{\underline i}</tex>.
Заметим теперь, что при <tex>i > x</tex> число <tex>x</tex>-раскрасок, в которых используется точно <tex>i</tex> цветов, равно <tex>0</tex> и при этом <tex>x^{\underline i}</tex> тоже равно <tex>0</tex>. Суммирование по <tex>i</tex> от <tex>1</tex> до <tex>n</tex> даст полное число способов.
'''Примечание''': в такой формулировке задача о поиске хроматического многочлена сводится к отысканию количества способов разбить граф на независимые множества, что в свою очередь также [[Примеры_NP-полных_языков#NP-полнота поиска максимального независимого множества | не разрешимо за полиномиальное время]].
}}
==См. также==
*[[Формула Уитни]]
