Изменения

Перейти к: навигация, поиск

Двудольные графы и раскраска в 2 цвета

Нет изменений в размере, 10:40, 24 апреля 2012
Раскраска в 2 цвета
|proof=
[[Файл: Bipartite_graph.png|thumb|200px300px|upright|Пример двудольного графа]]
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex> — 2-раскрашиваем. <tex>\chi(G) = 2</tex>.
272
правки

Навигация