200
правок
Изменения
Нет описания правки
{{Определение
|id=def_1
|definition=
'''Независимым множеством ''' (кокликой, англ. coclique''Independent set'') в графе <tex>G= (V, E)</tex> называется непустое множество <tex>S \subset VGV: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin EGE</tex>.
}}
{{Теорема
Зыкова
|statement=
Для [[Хроматический многочлен|хроматического многочлена]] графа <tex>G</tex> верна формула:<tex>P(G,x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}</tex>, где <tex>pt(G,i)</tex> — число способов разбить вершины <tex>G</tex> на <tex>i</tex> независимых множеств, <tex>n = |VGV|</tex>, а <tex> x^{\underline i} = x \cdot (x - 1) \cdot \ldots \cdot (x - i + 1)</tex> {{---}} нисходящая факториальная степень.
|proof=
}}
'''Примечание''': в такой формулировке задача о поиске хроматического многочлена сводится к отысканию количества способов разбить граф на независимые множества, что в свою очередь также [[Примеры_NP-полных_языков#NP-полнота поиска максимального независимого множества | не разрешимо за полиномиальное время]]. ==См. также==*[[Формула Уитни]] = Литература =Источники информации==# * ''Асанов М. О., Баранский В. А., Расин В. В.'' Дискретная математика: Графы, матроиды, алгоритмы. — {{---}} Ижевск: НИЦ «РХД», 2001. — С. 140—141140-141. — {{---}} '''ISBN 5-93972-076-5'''
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]