Раскраска двудольного графа в два цвета — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации)
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 2 участников)
Строка 4: Строка 4:
 
{{Теорема  
 
{{Теорема  
 
|statement=
 
|statement=
[[Основные определения теории графов|Граф]] <tex>2-</tex>[[Раскраска графа|раскрашиваемый]] тогда и только тогда, когда он [[Двудольные графы|двудольный]].
+
[[Основные определения теории графов|Граф]] <tex>2</tex>-[[Раскраска графа|раскрашиваемый]] тогда и только тогда, когда он [[Двудольные графы|двудольный]].
 
|proof=
 
|proof=
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex>  —  <tex>2-</tex>раскрашиваем. <tex>\chi(G) = 2</tex>.
+
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W, E)</tex>  —  <tex>2</tex>-раскрашиваем. <tex>\chi(G) = 2</tex>.
  
Если же граф <tex>2-</tex> раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольны.
+
Если же граф <tex>2</tex>-раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольны.
 
}}
 
}}
  
Строка 19: Строка 19:
 
|proof=
 
|proof=
  
<tex>\Rightarrow</tex> Рассмотрим двудольный граф. Начнем цикл в доле <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы вернуться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным.
+
<tex>\Rightarrow</tex>  
 +
:Рассмотрим двудольный граф. Начнем цикл в доле <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы вернуться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным.
  
<tex>\Leftarrow</tex> Пусть ненулевой граф <tex> G </tex> [[k-связность|связен]] и не имеет циклов нечетной длины. Выберем произвольно вершину <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>\Leftarrow</tex>  
 
+
:Пусть ненулевой граф <tex> G </tex> [[k-связность|связен]] и не имеет циклов нечетной длины. Выберем произвольно вершину <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> 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> они образуют цикл нечётной длины, что невозможно.
 
 
}}
 
}}
  

Текущая версия на 19:42, 4 сентября 2022

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

Теорема:
Граф [math]2[/math]-раскрашиваемый тогда и только тогда, когда он двудольный.
Доказательство:
[math]\triangleright[/math]

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

Если же граф [math]2[/math]-раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольны.
[math]\triangleleft[/math]

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

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

[math]\Rightarrow[/math]

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

[math]\Leftarrow[/math]

Пусть ненулевой граф [math] G [/math] связен и не имеет циклов нечетной длины. Выберем произвольно вершину [math] u [/math] и разобьем множество всех вершин на два непересекающихся множества [math] U [/math] и [math] V [/math] так, чтобы в [math] U [/math] лежали вершины [math] v_0 [/math], такие что кратчайшая цепь [math](u, v_0)[/math] была чётной длины, а в [math] V [/math] соответственно вершины [math]v_1[/math], для которых длина цепи [math](u, v_1)[/math] — нечётная. При этом [math] u \in U [/math]. В графе [math] G [/math] нет ребер [math]ab[/math], таких что [math]a, b [/math] лежат одновременно в [math] U [/math] и [math]V[/math]. Докажем это от противного. Пусть [math]a, b \in U [/math]. Зададим [math] P_0 [/math] — кратчайшая [math] (u, a) [/math] цепь, а [math] P_1 [/math] — кратчайшая [math] (u, b) [/math] цепь. Обе цепи четной длины. Пусть [math] v_0 [/math] — последняя вершина цепи [math] P_0 [/math], принадлежащая [math] P_1 [/math]. Тогда подцепи от [math] u [/math] до [math] v_0 [/math] в [math] P_0[/math] и [math]P_1[/math] имеют одинаковую длину (иначе бы, пройдя по более короткой подцепи от [math]u[/math] до [math]v_0[/math] мы смогли бы найти более короткую цепь от [math] u [/math] до [math] a [/math] или от [math] u [/math] до [math] b [/math], чем цепь [math] P_0 [/math] или [math] P_1 [/math] ). Так как подцепи от [math] v_0 [/math] до [math] a [/math] и от [math] v_0 [/math] до [math] b [/math] в цепях [math] P_0 [/math] и [math] P_1 [/math] имеют одинаковую четность, а значит в сумме с ребром [math] ab [/math] они образуют цикл нечётной длины, что невозможно.
[math]\triangleleft[/math]

Следствие

Алгоритм проверки графа на двудольность, используя обход в глубину

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

Алгоритм проверки графа на двудольность, используя обход в ширину

Произведём серию поисков в ширину. Т.е. будем запускать поиск в ширину из каждой непосещённой вершины. Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю. В процессе поиска в ширину, если мы идём в какую-то новую вершину, то мы помещаем её в долю, отличную от доли текущей вершину. Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. В противном случае граф двудольным не является. По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли.

См. также

Источники информации