Двудольные графы и раскраска в 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>
 
}}
 
}}
 
[[Файл:Двудольный граф.jpg|thumb|upright|Пример двудольного графа]]
 
  
 
== Раскраска в 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

Определение:
Неориентированный граф [math]G = (W,E)[/math] называется двудольным, если множество его вершин можно разбить на две части [math] U \cup V = W , \mid U\mid \gt 0, \mid V\mid \gt 0[/math], так, что ни одна вершина в [math]U[/math] не соединена с вершинами в [math]U[/math] и ни одна вершина в [math]V[/math] не соединена с вершинами в [math]V[/math].


Теорема Кенига

Теорема (Кёниг):
Граф [math] G [/math] с конечным числом вершин является двудольным [math] \iff [/math] когда все циклы в графе [math] G [/math] имеют чётную длину.
Доказательство:
[math]\triangleright[/math]

Достаточность.

Пример двудольного графа


Рассмотрим двудольный граф. Начнем цикл в доли [math] U [/math]. Нужно пройти по четному числу ребер, чтобы подняться в [math] U [/math] снова. Следовательно, при замыкании цикла число ребер будет четным. Очевидно, что в двудольном графе нет петель.


Необходимость.

Пусть ненулевой граф [math] G [/math] связен и не имеет циклов нечетной длины. Выберем произвольно вершину [math] u [/math] и разобьем множество всех вершин на на два непересекающихся множества [math] V_0 [/math] и [math] V_1 [/math] так, чтобы в [math] V_0 [/math] лежали вершины [math] v_0 [/math], такие что кратчайшая цепь [math](u, v_0)[/math] была чётной длины, а в [math] V_1 [/math] соответственно вершины [math]v_1[/math], для которых длина цепи [math](u, v_1)[/math] - нечётная. При этом [math] u \in V_0 [/math]

В [math] G [/math]
[math]\triangleleft[/math]

Раскраска в 2 цвета

Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества [math]\Rightarrow[/math] граф [math]G = (W,E)[/math] - 2 - раскрашиваем. [math]\chi(G) = 2[/math].

Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину. На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в множество [math] U [/math]. То есть ставим метку [math] 1 [/math]. Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как [math] 2 [/math] (то есть добавляем во множество [math] V [/math] ) и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.


Источники

1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
2. Харари Ф. - Теория графов. ISBN 978-5-397-00622-4

См. также