|
|
| (не показаны 22 промежуточные версии 2 участников) |
| Строка 1: |
Строка 1: |
| − | {{Определение
| + | #перенаправление [[Раскраска двудольного графа в два цвета]] |
| − |
| |
| − | |definition=
| |
| − | Неориентированный граф <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 цвета ==
| |
| − | | |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Граф 2-раскрашиваемый тогда и только тогда, когда он двудольный.
| |
| − | |proof=
| |
| − | Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex> — 2-раскрашиваем. <tex>\chi(G) = 2</tex>.
| |
| − | | |
| − | Если же граф 2-раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольным.
| |
| − | }}
| |
| − | | |
| − | ==Теорема Кенига==
| |
| − | {{Теорема
| |
| − | |about=
| |
| − | Кениг
| |
| − | |statement=
| |
| − | Граф <tex> G </tex> является двудольным тогда и только тогда, когда все циклы в графе <tex> G </tex> имеют чётную длину.
| |
| − | |proof=
| |
| − | | |
| − | ''Достаточность.''
| |
| − | | |
| − | Рассмотрим двудольный граф. Начнем цикл в доле <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 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>), значит граф не двудольный.
| |
| − | | |
| − | | |
| − | == Источники ==
| |
| − | 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| Графы. Раскраски и укладки.]
| |
| − | | |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Раскраски графов]]
| |
