Двудольные графы и раскраска в 2 цвета — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показаны 53 промежуточные версии 7 участников)
Строка 1: Строка 1:
{{Определение
+
#перенаправление [[Раскраска двудольного графа в два цвета]]
|definition=
 
Неориентированный граф <tex>G = (W,E)</tex> называется '''двудольным''', если множество его вершин можно разбить на две части  <tex> U \cup V = W , \mid U\mid > 0, \mid V\mid > 0</tex>, так, что ни одна вершина в <tex>U</tex> не соединена с вершинами в <tex>U</tex> и ни одна вершина в <tex>V</tex> не соединена с вершинами в <tex>V</tex>.
 
}}
 
 
 
Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества <tex>\Rightarrow</tex> граф <tex>G = (W,E)</tex> - 2-раскрашиваем. <tex>\chi(G) = 2</tex>.
 

Текущая версия на 22:32, 22 ноября 2016