Изменения

'''Независимым множеством ''' (кокликой, англ. coclique''Independent set'') в графе <tex>G= (V, E)</tex> называется непустое множество <tex>S \subset VGV: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin EGE</tex>.

Для [[Хроматический многочлен|хроматического многочлена]] графа <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 = |V|</tex>, а <tex> x^{\underline i} = x \cdot (x - 1) \cdot \ldots \cdot (x - i + 1)</tex> {{---}} нисходящая факториальная степень.

Найдём число <tex>x</tex>-раскрасок графа <tex>G</tex>В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в которых используется точно одно независимое множество. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской <tex>i</tex> цветов (<tex>1 \le i \le x</tex>). Для получения такой доступными цветами получим искомое число способов раскраски сначала выберем одним из <tex>pt(G,i)</tex> способов разбиение графа <tex>G</tex> на в <tex>i</tex> независимых множеств, а затем одним из <tex>{x\choose i} i! = x^{\underline i}</tex> способов <tex>i</tex> упорядоченных цветов из <tex>x</tex>.

При Теперь проделаем это более формально. Подсчитаем число раскрасок графа <tex>G</tex>, в которых используется точно <tex>i </tex> цветов, для этого его нужно разбить на <tex>i</tex> независимых множеств и вершины в каждом таком классе покрасить в один из <tex>i</tex> цветов, отличный от всех других множеств, так как мы не делаем никаких предположений о связи между классами.  Рассмотрим случай, где <tex>1 \leqslant i \leqslant x</tex> число . Чтобы получить такую раскраску зафиксируем какое-нибудь разбиение множества вершин графа <tex>G</tex> на <tex>i</tex> независимых множеств, затем берем один из классов в разбиении и раскрашиваем его в один из <tex>x</tex>цветов, потом берем следующий класс и окрашиваем его вершины в одинаковый цвет любой из <tex>x -1</tex> оставшихся красок и т.д. Всего таких способов разбиения существует <tex>pt(G,i)</tex>.Следовательно, перебрав все возможные разбиения на <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-полнота поиска максимального независимого множества | не разрешимо за полиномиальное время]].  ==См. также==*[[Формула Уитни]] = Литература =Источники информации==# * ''Асанов М. О., Баранский В. А., Расин В. В.'' Дискретная математика: Графы, матроиды, алгоритмы. — {{---}} Ижевск: НИЦ «РХД», 2001. — С. 140—141140-141. — {{---}} '''ISBN 5-93972-076-5'''