Изменения

'''Независимым множеством''' (кокликой, англ. ''CocliqueIndependent set'') в графе <tex>G = (V, E)</tex> называется непустое множество <tex>S \subset V: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin E</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>x</tex> цветов. Теперь проделаем это более формально. Подсчитаем число раскрасок графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов, для этого его нужно разбить на <tex>i</tex> независимых множеств и вершины в каждом таком классе покрасить в один из <tex>i</tex> цветов, отличный от всех других множеств, так как мы не делаем никаких предположений о связи между классами.  Рассмотрим случай, где <tex>1 \leqslant i \leqslant x</tex>. Чтобы получить такую раскраскусначала одним из <tex>pt(G,i)</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> даёт даст полное число способов.Отметим, что когда мы красим фиксированное разбиение, мы не делаем никаких предположений о связи самих классов, поэтому их необходимо красить в различные цвета. На этом этапе есть что-то общее с раскраской полного графа.