|
|
| (не показано 46 промежуточных версий 6 участников) |
| Строка 1: |
Строка 1: |
| − | Неориентированный граф <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> \iff </tex> когда все циклы четные.
| |
| − | |proof=
| |
| − | | |
| − | ''Достаточность.''
| |
| − | | |
| − | Рассмотрим двудольный граф. Начнем цикл в доли <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы подняться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным.
| |
| − | | |
| − | ''Необходимость.''
| |
| − | | |
| − | Если граф несвязный, то проведем доказательство отдельно для каждой компоненты.
| |
| − | | |
| − | Пусть граф связный и все циклы в нем четные. Выделим произвольную вершину <tex> v_0 </tex> и найдем произвольные цепи между <tex> v_0 </tex> и всеми остальными вершинами (например, самые короткие алгоритмом Дейкстры). Если одна цепь <tex>(v_0, v_i)</tex> нечетной длины, то и любая цепь <tex>(v_0, v_i)</tex> нечетная, иначе бы эти цепи образовали нечетный цикл.
| |
| − | | |
| − | Аналогично, если <tex>(v_0, v_i)</tex> — четная, то и любая <tex>(v_0, v_i)</tex> — четная. Разобьем вершины на две доли: в одну войдет вершина <tex> v_0 </tex> и все, находящиеся от <tex> v_0 </tex> на четном расстоянии; в другую долю поместим все вершины, находящиеся от <tex> v_0 </tex> на нечетном расстоянии. Если вершины <tex> u_1 </tex> и <tex> u_2 </tex> принадлежат одной доле, то между ними не может быть ребра, иначе это ребро вместе с цепями <tex>(v_0, u_1)</tex> и <tex>(v_0, u_2)</tex> образовали бы нечетный цикл.
| |
| − | }}
| |
| − | | |
| − | | |
| − | === Раскраска в 2 цвета ===
| |
| − | | |
| − | [[Файл:Двудольный граф.jpg|thumb|upright|Пример двудольного графа]] | |
| − | | |
| − | Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества <tex>\Rightarrow</tex> граф <tex>G = (W,E)</tex> - 2-раскрашиваем. <tex>\chi(G) = 2</tex>.
| |
| − | | |
| − | Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину.
| |
| − | На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в множество <tex> U </tex>. То есть ставим метку <tex> 1 </tex>. Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как <tex> 2 </tex> (то есть добавляем во множество <tex> V </tex> ) и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.
| |
| − | | |
| − | | |
| − | ===См. также ===
| |
| − | * [http://rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout| Графы. Раскраски и укладки.]
| |
