53
правки
Изменения
Новая статья
{{В разработке}}
{{Определение
|definition=
Независимым множеством (кокликой, англ. coclique) в графе <tex>G</tex> называется непустое <tex>S \subset VG: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin EG</tex>.
}}
{{Теорема
|about=
Зыкова
|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> независимых множеств.
|proof=
}}
== Литература ==
# ''Асанов М. О., Баранский В. А., Расин В. В.'' Дискретная математика: Графы, матроиды, алгоритмы. — Ижевск: НИЦ «РХД», 2001. — С. 140—141. — '''ISBN 5-93972-076-5'''
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
{{Определение
|definition=
Независимым множеством (кокликой, англ. coclique) в графе <tex>G</tex> называется непустое <tex>S \subset VG: \forall v,u \in S\</tex> ребро <tex>(v,u) \notin EG</tex>.
}}
{{Теорема
|about=
Зыкова
|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> независимых множеств.
|proof=
}}
== Литература ==
# ''Асанов М. О., Баранский В. А., Расин В. В.'' Дискретная математика: Графы, матроиды, алгоритмы. — Ижевск: НИЦ «РХД», 2001. — С. 140—141. — '''ISBN 5-93972-076-5'''
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
