Двудольные графы и раскраска в 2 цвета — различия между версиями
Строка 14: | Строка 14: | ||
''Достаточность.'' | ''Достаточность.'' | ||
+ | |||
+ | [[Файл:Двудольный граф.jpg|thumb|upright|Пример двудольного графа]] | ||
+ | |||
Рассмотрим двудольный граф. Начнем цикл в доли <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы подняться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным. Очевидно, что в двудольном графе нет петель. | Рассмотрим двудольный граф. Начнем цикл в доли <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы подняться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным. Очевидно, что в двудольном графе нет петель. | ||
+ | |||
''Необходимость.'' | ''Необходимость.'' | ||
− | Пусть ненулевой граф <tex> G </tex> связен и не имеет циклов нечетной длины. Выберем произвольно вершину <tex> u </tex> и разобьем множество всех вершин на на два непересекающихся множества <tex> V_0 </tex> и <tex> V_1 </tex> так, чтобы в <tex> V_0 </tex> лежали вершины <tex> v_0 </tex>,такие что кратчайшая цепь <tex>(u, v_0)</tex> была чётной длины, а в <tex> V_1 </tex> соответственно вершины <tex>v_1</tex>, для которых длина цепи <tex>(u, v_1)</tex> - нечётная. При этом <tex> u \in V_0 </tex> | + | |
+ | Пусть ненулевой граф <tex> G </tex> связен и не имеет циклов нечетной длины. Выберем произвольно вершину <tex> u </tex> и разобьем множество всех вершин на на два непересекающихся множества <tex> V_0 </tex> и <tex> V_1 </tex> так, чтобы в <tex> V_0 </tex> лежали вершины <tex> v_0 </tex>, такие что кратчайшая цепь <tex>(u, v_0)</tex> была чётной длины, а в <tex> V_1 </tex> соответственно вершины <tex>v_1</tex>, для которых длина цепи <tex>(u, v_1)</tex> - нечётная. При этом <tex> u \in V_0 </tex> | ||
В <tex> G </tex> | В <tex> G </tex> | ||
}} | }} | ||
− | |||
− | |||
== Раскраска в 2 цвета == | == Раскраска в 2 цвета == | ||
− | Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества <tex>\Rightarrow</tex> граф <tex>G = (W,E)</tex> - 2-раскрашиваем. <tex>\chi(G) = 2</tex>. | + | Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества <tex>\Rightarrow</tex> граф <tex>G = (W,E)</tex> - 2 - раскрашиваем. <tex>\chi(G) = 2</tex>. |
Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину. | Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину. | ||
Строка 33: | Строка 36: | ||
− | + | == Источники == | |
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br /> | 1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br /> | ||
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4''' | 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| Графы. Раскраски и укладки.] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Раскраски графов]] | [[Категория: Раскраски графов]] |
Версия 03:05, 14 января 2012
Определение: |
Неориентированный граф | называется двудольным, если множество его вершин можно разбить на две части , так, что ни одна вершина в не соединена с вершинами в и ни одна вершина в не соединена с вершинами в .
Теорема Кенига
Теорема (Кёниг): |
Граф с конечным числом вершин является двудольным когда все циклы в графе имеют чётную длину. |
Доказательство: |
Достаточность.
Пусть ненулевой граф В связен и не имеет циклов нечетной длины. Выберем произвольно вершину и разобьем множество всех вершин на на два непересекающихся множества и так, чтобы в лежали вершины , такие что кратчайшая цепь была чётной длины, а в соответственно вершины , для которых длина цепи - нечётная. При этом |
Раскраска в 2 цвета
Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества
граф - 2 - раскрашиваем. .Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину. На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в множество
. То есть ставим метку . Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как (то есть добавляем во множество ) и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.
Источники
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
2. Харари Ф. - Теория графов. ISBN 978-5-397-00622-4