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

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[Раскраска двудольного графа в два цвета]]
+
== Раскраска в 2 цвета ==
 +
 
 +
{{Теорема
 +
|statement=
 +
[[Основные определения теории графов|Граф]] <tex>2-</tex>[[Раскраска графа|раскрашиваемый]] тогда и только тогда, когда он [[Двудольные графы|двудольный]].
 +
|proof=
 +
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex>  —  <tex>2-</tex>раскрашиваем. <tex>\chi(G) = 2</tex>.
 +
 
 +
Если же граф <tex>2-</tex> раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольны.
 +
}}
 +
 
 +
==Теорема Кёнига==
 +
{{Теорема
 +
|about=
 +
Кёниг
 +
|statement=
 +
Граф <tex> G </tex> является двудольным тогда и только тогда, когда все [[Основные определения теории графов #def_graph_cycle_1|циклы]] в графе <tex> G </tex> имеют чётную длину.
 +
|proof=
 +
 
 +
''Достаточность.''
 +
 
 +
Рассмотрим двудольный граф. Начнем цикл в доле <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы вернуться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным.
 +
 
 +
''Необходимость.''
 +
 
 +
Пусть ненулевой граф <tex> G </tex> [[k-связность|связен]] и не имеет циклов нечетной длины. Выберем произвольно вершину <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 U </tex>. Зададим <tex> P_0 </tex> — кратчайшая <tex> (u, a) </tex> цепь, а <tex> P_1 </tex> — кратчайшая <tex> (u, b) </tex> цепь. Обе цепи четной длины. Пусть <tex> v_0 </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>u</tex> до <tex>v_0</tex> мы смогли бы найти более короткую цепь от <tex> u </tex> до <tex> a </tex> или от <tex> u </tex> до <tex> b </tex>, чем цепь <tex> P_0 </tex> или <tex> P_1 </tex>  ). Так как подцепи от <tex> v_0 </tex> до <tex> a </tex> и от <tex> v_0 </tex> до <tex> b </tex> в цепях <tex> P_0 </tex> и <tex> P_1 </tex> имеют одинаковую четность, а значит в сумме с ребром <tex> ab </tex> они образуют цикл нечётной длины, что невозможно.
 +
}}
 +
 
 +
== Следствие ==
 +
 
 +
===Алгоритм проверки графа на двудольность, используя обход в глубину===
 +
 
 +
Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один [[Обход в глубину, цвета вершин|проход в глубину]].
 +
На каждом шаге обхода в глубину помечаем вершину. Допустим, мы пошли в первую вершину — помечаем её как <tex> 1 </tex>. Затем просматриваем все смежные вершины, и если не помечена вершина, то на ней ставим пометку <tex> 2 </tex> и рекурсивно переходим в нее. Если же она помечена и на ней стоит та же пометка, что и у той, из которой шли (в нашем случае <tex> 1 </tex>), значит граф не двудольный.
 +
 
 +
===Алгоритм проверки графа на двудольность, используя обход в ширину===
 +
 
 +
Произведём серию поисков в [[Обход в ширину|ширину]]. Т.е. будем запускать поиск в ширину из каждой непосещённой вершины. Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю. В процессе поиска в ширину, если мы идём в какую-то новую вершину, то мы помещаем её в долю, отличную от доли текущей вершину. Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. В противном случае граф двудольным не является.
 +
По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли.
 +
 
 +
==См. также ==
 +
* [[Укладка графа на плоскости|Укладка графа на плоскости.]]
 +
* [[Раскраска графа|Раскраска графа]]
 +
 
 +
== Источники информации ==
 +
* Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы.
 +
* ''Харари Ф.'' Теория графов. /пер. с англ. — изд. 2-е — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
 +
* [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 Обход в ширину. Реализации.]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Раскраски графов]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)