Двудольные графы и раскраска в 2 цвета — различия между версиями
| Строка 1: | Строка 1: | ||
| + | {{Определение | ||
| + | |||
| + | |definition= | ||
Неориентированный граф <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>. | Неориентированный граф <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= | |about= | ||
Кёниг | Кёниг | ||
|statement= | |statement= | ||
| − | Граф является двудольным <tex> \iff </tex> когда все циклы | + | Граф <tex> G </tex> с конечным числом вершин является двудольным <tex> \iff </tex> когда все циклы в графе <tex> G </tex> имеют чётную длину. |
|proof= | |proof= | ||
''Достаточность.'' | ''Достаточность.'' | ||
| − | Рассмотрим двудольный граф. Начнем цикл в доли <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> | |
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
| + | [[Файл:Двудольный граф.jpg|thumb|upright|Пример двудольного графа]] | ||
| − | + | == Раскраска в 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>. | ||
Версия 10:58, 13 января 2012
| Определение: |
| Неориентированный граф называется двудольным, если множество его вершин можно разбить на две части , так, что ни одна вершина в не соединена с вершинами в и ни одна вершина в не соединена с вершинами в . |
Теорема Кенига
| Теорема (Кёниг): |
Граф с конечным числом вершин является двудольным когда все циклы в графе имеют чётную длину. |
| Доказательство: |
|
Достаточность. Рассмотрим двудольный граф. Начнем цикл в доли . Нужно пройти по четному числу ребер, чтобы подняться в снова. Следовательно, при замыкании цикла число ребер будет четным. Очевидно, что в двудольном графе нет петель. Необходимость. Пусть ненулевой граф связен и не имеет циклов нечетной длины. Выберем произвольно вершину и разобьем множество всех вершин на на два непересекающихся множества и так, чтобы в лежали вершины ,такие что кратчайшая цепь была чётной длины, а в соответственно вершины , для которых длина цепи - нечётная. При этом В |
Раскраска в 2 цвета
Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества граф - 2-раскрашиваем. .
Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину. На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в множество . То есть ставим метку . Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как (то есть добавляем во множество ) и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.
