65
правок
Изменения
Нет описания правки
{{Определение
|definition=
Независимым множеством (кокликой, англ. coclique) в графе <tex>G</tex> называется непустое <tex>S \subset V: \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>.
|proof=
Пусть в <tex>x</tex>-раскраске графа <tex>G</tex>, используется точно <tex>i</tex> цветов.
