68
правок
Изменения
Нет описания правки
<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> {{---}} нисходящая факториальная степень.
|proof=
В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество, так как все они попарно не смежны. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской <tex>x</tex> доступными цветами получим искомое число способов раскраски графа <tex>G</tex> в <tex>x</tex> цветов.
Теперь проделаем это более формально. Подсчитаем число раскрасок графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов, для этого его нужно разбить на <tex>i</tex> независимых множеств и вершины в каждом таком классе покрасить в один из <tex>i</tex> цветов, отличный от всех других множеств, так как мы не делаем никаких предположений о связи между классами.
