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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Кенига)
Строка 1: Строка 1:
{{Определение
+
== Двудольный граф ==
+
 
|definition=
+
[[Файл: Bipartite_graph.png|300px|thumb|center|Пример [[Основные_определения_теории_графов#Двудольный_граф |двудольного]] графа]]
Неориентированный граф <tex> G =(W, E) </tex> называется '''двудольным''', если множество его вершин можно разбить на две части <tex>U \cup V = W , |U| > 0, |V| > 0</tex>, так, что ни одна вершина в <tex>U</tex> не соединена с вершинами в <tex> U </tex> и ни одна вершина в <tex> V </tex> не соединена с вершинами в <tex>V</tex>.
 
}}
 
[[Файл: Bipartite_graph.png|thumb|right|300px|Пример двудольного графа]]
 
  
 
== Раскраска в 2 цвета ==
 
== Раскраска в 2 цвета ==
Строка 10: Строка 7:
 
{{Теорема  
 
{{Теорема  
 
|statement=
 
|statement=
Граф 2-раскрашиваемый тогда и только тогда, когда он двудольный.
+
Граф 2-раскрашиваемый тогда и только тогда, когда он двудольный (англ. '' bipartite graph'' or ''bigraph'').
 
|proof=
 
|proof=
 
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex>  —  2-раскрашиваем. <tex>\chi(G) = 2</tex>.
 
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex>  —  2-раскрашиваем. <tex>\chi(G) = 2</tex>.
Строка 17: Строка 14:
 
}}
 
}}
  
==Теорема Кенига==
+
==Теорема Кёнига==
 
{{Теорема  
 
{{Теорема  
 
|about=
 
|about=
Кениг
+
Кёниг
 
|statement=
 
|statement=
 
Граф <tex> G </tex> является двудольным тогда и только тогда, когда все циклы в графе <tex> G </tex> имеют чётную длину.
 
Граф <tex> G </tex> является двудольным тогда и только тогда, когда все циклы в графе <tex> G </tex> имеют чётную длину.
Строка 36: Строка 33:
 
}}
 
}}
  
== Алгоритм ==
+
== Следствие ==
 +
 
 +
===Алгоритм проверки графа на двудольность, используя обход в глубину===
  
Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину.
+
Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину (англ. ''Depth-first search'').
На каждом шаге обхода в глубину помечаем вершину. Допустим мы пошли в первую вершину — помечаем её как <tex> 1 </tex>. Затем просматриваем все смежные вершины и если не помечена вершина, то на ней ставим пометку <tex> 2 </tex> и рекурсивно переходим в нее. Если же она помечена и на ней стоит та же пометка, что и у той, из которой шли (в нашем случае <tex> 1 </tex>), значит граф не двудольный.
+
На каждом шаге обхода в глубину помечаем вершину. Допустим, мы пошли в первую вершину — помечаем её как <tex> 1 </tex>. Затем просматриваем все смежные вершины, и если не помечена вершина, то на ней ставим пометку <tex> 2 </tex> и рекурсивно переходим в нее. Если же она помечена и на ней стоит та же пометка, что и у той, из которой шли (в нашем случае <tex> 1 </tex>), значит граф не двудольный.
  
 +
===Алгоритм проверки графа на двудольность, используя обход в ширину===
  
== Источники ==
+
Произведём серию поисков в ширину (англ. ''Breadth-first search''). Т.е. будем запускать поиск в ширину из каждой непосещённой вершины. Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю. В процессе поиска в ширину, если мы идём в какую-то новую вершину, то мы помещаем её в долю, отличную от доли текущей вершину. Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. В противном случае граф двудольным не является.
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| Графы. Раскраски и укладки.]
 
* [http://rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout| Графы. Раскраски и укладки.]
 +
 +
== Источники ==
 +
* Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы.
 +
* Харари Ф. - Теория графов.
 +
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) Теорема Кёнига]
 +
* [http://e-maxx.ru/algo/bipartite_checking MAXimal :: algo :: Проверка графа на двудольность]
 +
* [http://www.e-maxx.ru/algo/dfs Обход в глубину. Реализации.]
 +
* [http://e-maxx.ru/algo/bfs Обход в ширину. Реализации.]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Раскраски графов]]
 
[[Категория: Раскраски графов]]

Версия 02:15, 26 января 2016

Двудольный граф

Пример двудольного графа

Раскраска в 2 цвета

Теорема:
Граф 2-раскрашиваемый тогда и только тогда, когда он двудольный (англ. bipartite graph or bigraph).
Доказательство:
[math]\triangleright[/math]

Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф [math]G = (W, E)[/math] — 2-раскрашиваем. [math]\chi(G) = 2[/math].

Если же граф 2-раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольным.
[math]\triangleleft[/math]

Теорема Кёнига

Теорема (Кёниг):
Граф [math] G [/math] является двудольным тогда и только тогда, когда все циклы в графе [math] G [/math] имеют чётную длину.
Доказательство:
[math]\triangleright[/math]

Достаточность.

Рассмотрим двудольный граф. Начнем цикл в доле [math] U [/math]. Нужно пройти по четному числу ребер, чтобы вернуться в [math] U [/math] снова. Следовательно, при замыкании цикла число ребер будет четным.

Необходимость.

Пусть ненулевой граф [math] G [/math] связен и не имеет циклов нечетной длины. Выберем произвольно вершину [math] u [/math] и разобьем множество всех вершин на два непересекающихся множества [math] U [/math] и [math] V [/math] так, чтобы в [math] U [/math] лежали вершины [math] v_0 [/math], такие что кратчайшая цепь [math](u, v_0)[/math] была чётной длины, а в [math] V [/math] соответственно вершины [math]v_1[/math], для которых длина цепи [math](u, v_1)[/math] — нечётная. При этом [math] u \in U [/math].

В графе [math] G [/math] нет ребер [math]ab[/math], таких что [math]a, b [/math] лежат одновременно в [math] U [/math] и [math]V[/math]. Докажем это от противного. Пусть [math]a, b \in U [/math]. Зададим [math] P_0 [/math] — кратчайшая [math] (u, a) [/math] цепь, а [math] P_1 [/math] — кратчайшая [math] (u, b) [/math] цепь. Обе цепи четной длины. Пусть [math] v_0 [/math] — последняя вершина цепи [math] P_0 [/math], принадлежащая [math] P_1 [/math]. Тогда подцепи от [math] u [/math] до [math] v_0 [/math] в [math] P_0[/math] и [math]P_1[/math] имеют одинаковую длину (иначе бы, пройдя по более короткой подцепи от [math]u[/math] до [math]v_0[/math] мы смогли бы найти более короткую цепь от [math] u [/math] до [math] a [/math] или от [math] u [/math] до [math] b [/math], чем цепь [math] P_0 [/math] или [math] P_1 [/math] ). Так как подцепи от [math] v_0 [/math] до [math] a [/math] и от [math] v_0 [/math] до [math] b [/math] в цепях [math] P_0 [/math] и [math] P_1 [/math] имеют одинаковую четность, а значит в сумме с ребром [math] ab [/math] они образуют цикл нечётной длины, что невозможно.
[math]\triangleleft[/math]

Следствие

Алгоритм проверки графа на двудольность, используя обход в глубину

Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину (англ. Depth-first search). На каждом шаге обхода в глубину помечаем вершину. Допустим, мы пошли в первую вершину — помечаем её как [math] 1 [/math]. Затем просматриваем все смежные вершины, и если не помечена вершина, то на ней ставим пометку [math] 2 [/math] и рекурсивно переходим в нее. Если же она помечена и на ней стоит та же пометка, что и у той, из которой шли (в нашем случае [math] 1 [/math]), значит граф не двудольный.

Алгоритм проверки графа на двудольность, используя обход в ширину

Произведём серию поисков в ширину (англ. Breadth-first search). Т.е. будем запускать поиск в ширину из каждой непосещённой вершины. Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю. В процессе поиска в ширину, если мы идём в какую-то новую вершину, то мы помещаем её в долю, отличную от доли текущей вершину. Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. В противном случае граф двудольным не является. По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли.

См. также

Источники