http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=94.241.200.200&*Викиконспекты - Вклад участника [ru]2026-06-10T19:25:46ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%97%D1%8B%D0%BA%D0%BE%D0%B2%D0%B0&diff=75081Формула Зыкова2020-10-05T21:49:06Z<p>94.241.200.200: </p>
<hr />
<div>{{Определение<br />
|id=def_1<br />
|definition=<br />
'''Независимым множеством''' (англ. ''Independent set'') в графе <tex>G = (V, E)</tex> называется непустое множество <tex>S \subset V: \forall v,u \in S</tex> ребро <tex>(v,u) \notin E</tex>.<br />
}}<br />
{{Теорема<br />
|about=<br />
Зыкова<br />
|statement=<br />
Для [[Хроматический многочлен|хроматического многочлена]] графа <tex>G</tex> верна формула:<br />
<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> {{---}} нисходящая факториальная степень.<br />
|proof=<br />
В правильной раскраске вершины, имеющие одинаковый цвет, не смежны, поэтому все такие вершины могут быть объединены в одно независимое множество. Перебрав все возможные разбиения на независимые множества с последующей их всевозможной покраской <tex>x</tex> доступными цветами получим искомое число способов раскраски графа <tex>G</tex> в <tex>x</tex> цветов.<br />
<br />
Теперь проделаем это более формально. Подсчитаем число раскрасок графа <tex>G</tex>, в которых используется точно <tex>i</tex> цветов, для этого его нужно разбить на <tex>i</tex> независимых множеств и вершины в каждом таком классе покрасить в один из <tex>i</tex> цветов, отличный от всех других множеств, так как мы не делаем никаких предположений о связи между классами. <br />
<br />
Рассмотрим случай, где <tex>1 \leqslant i \leqslant x</tex>. Чтобы получить такую раскраску зафиксируем какое-нибудь разбиение множества вершин графа <tex>G</tex> на <tex>i</tex> независимых множеств, затем берем один из классов в разбиении и <br />
раскрашиваем его в один из <tex>x</tex> цветов, потом берем следующий класс и окрашиваем его вершины в одинаковый цвет любой из <tex>x - 1</tex> оставшихся красок и т.д. Всего таких способов разбиения существует <tex>pt(G,i)</tex>.<br />
Следовательно, перебрав все возможные разбиения на <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>.<br />
<br />
Заметим теперь, что при <tex>i > x</tex> число <tex>x</tex>-раскрасок, в которых используется точно <tex>i</tex> цветов, равно <tex>0</tex> и при этом <tex>x^{\underline i}</tex> тоже равно <tex>0</tex>. <br />
<br />
Суммирование по <tex>i</tex> от <tex>1</tex> до <tex>n</tex> даст полное число способов.<br />
}}<br />
'''Примечание''': в такой формулировке задача о поиске хроматического многочлена сводится к отысканию количества способов разбить граф на независимые множества, что в свою очередь также [[Примеры_NP-полных_языков#NP-полнота поиска максимального независимого множества | не разрешимо за полиномиальное время]]. <br />
<br />
==См. также==<br />
*[[Формула Уитни]]<br />
<br />
==Источники информации==<br />
* ''Асанов М. О., Баранский В. А., Расин В. В.'' Дискретная математика: Графы, матроиды, алгоритмы. {{---}} Ижевск: НИЦ «РХД», 2001. С. 140-141. {{---}} '''ISBN 5-93972-076-5'''<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Раскраски графов]]</div>94.241.200.200