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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Кенига)
 
(не показано 40 промежуточных версий 6 участников)
Строка 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>.
 
}}
 
 
 
==Теорема Кенига==
 
{{Теорема
 
|about=
 
Кёниг
 
|statement=
 
Граф <tex> G </tex> с конечным числом вершин является двудольным <tex> \iff </tex> когда все циклы в графе <tex> G </tex> имеют чётную длину.
 
|proof=
 
 
 
''Достаточность.''
 
 
 
[[Файл:Двудольный граф.jpg|thumb|upright|Пример двудольного графа]]
 
 
 
 
 
Рассмотрим двудольный граф. Начнем цикл в доли <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы подняться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным. Очевидно, что в двудольном графе нет петель.
 
 
 
 
 
''Необходимость.''
 
 
 
Пусть ненулевой граф <tex> G </tex> связен и не имеет циклов нечетной длины. Выберем произвольно вершину <tex> u </tex> и разобьем множество всех вершин на на два непересекающихся множества <tex> U </tex> и <tex> V </tex> так, чтобы в <tex> U </tex> лежали вершины <tex> v_0 </tex>, такие что кратчайшая цепь <tex>(u, v_0)</tex> была чётной длины, а в <tex> V </tex> соответственно вершины <tex>v_1</tex>, для которых длина цепи <tex>(u, v_1)</tex> - нечётная. При этом <tex> u \in U </tex>.
 
 
 
В графе <tex> G </tex> нет ребер <tex>ab</tex>, таких что <tex>a, b </tex> лежат одновременно в <tex> U </tex>  и <tex>V</tex>. Поведем доказательство от противного. Пусть <tex>a, b \in V_0 </tex>. Зададим <tex> P_0 </tex> - кратчайшая <tex> (u, a) </tex> цепь, а <tex> P_1 </tex>- кратчайшая <tex> (u, b) </tex> цепь. Обе цепи четной длины. Пусть <tex> u </tex> - последняя вершина цепи <tex> P_0 </tex>, принадлежащая <tex> P_1 </tex>. Тогда подцепи от <tex> u </tex> до <tex> v_0  </tex> в <tex> P_0</tex> и <tex>P_1</tex> имеют одинаковую длину (иначе бы противоречили выбору <tex> P_0  </tex> и <tex> P_1 </tex>). А так как подцепи одинаковы, то чётность у них одинакова, а значит в сумме с ребром <tex> ab </tex> они образуют цикл нечётной длины, что невозможно.
 
}}
 
 
 
== Раскраска в 2 цвета ==
 
 
 
Так как множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества <tex>\Rightarrow</tex> граф <tex>G = (W,E)</tex> -  2 - раскрашиваем. <tex>\chi(G) = 2</tex>.
 
 
 
Так же, если граф 2 - раскрашиваем, значит множество его вершин можно разделить на два непересекающихся множества так, что в каждом из них не найдется двух смежных вершин, то граф является двудольным.
 
 
 
 
 
Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину.
 
На каждом шаге обхода в глубину помечаем вершину. Допустим мы пошли в первую вершину - помечаем её как <tex> 1 </tex>. Затем просматриваем все смежные вершины и если не помечена вершина, то на ней пометку <tex> 2 </tex> и рекурсивно переходим в нее. Если же она помечена и на ней стоит та же пометка, что и у той, из которой шли(в нашем случае <tex> 1 </tex>), значит граф не двудольный.
 
 
 
== Источники ==
 
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
 
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
 
 
 
==См. также ==
 
* [http://rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout| Графы. Раскраски и укладки.]
 
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Раскраски графов]]
 

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