Изменения

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

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

34 байта добавлено, 21:35, 22 ноября 2016
Раскраска в 2 цвета
{{Теорема
|statement=
Граф 2-[[Раскраска графа|раскрашиваемый ]] тогда и только тогда, когда он [[Двудольные графы|двудольный]] (англ. '' bipartite graph'' or ''bigraph'').
|proof=
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex> — 2-раскрашиваем. <tex>\chi(G) = 2</tex>.
Анонимный участник

Навигация