Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/Раскраска графа в два цвета — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Содержимое страницы заменено на «== Полиномиальный алгоритм для раскраски графа в два цвета == Постройте …»)
Строка 4: Строка 4:
  
  
[[Category:На проверку]]
+
[[Category:Нерешенные задачи]]
 
+
<!--Вообще-то, решения уже есть-->
==Стенин Сергей группа 974==
+
 
+
<m>
+
 
+
1. Граф можно покрасить в два цвета $\equiv$ граф двудольный
+
 
+
Если граф двудольный, то его вершины можно разбить на два множества так, что внутри одного множества вершины между собой не имеют ребер, поэтому можно в первом множестве их покрасить в красный цвет, а во втором - синий и получить раскраску в два цвета
+
 
+
Если граф можно покрасить в два цвета так, чтобы не было ребер, у которых на разных концах один и тот же цвет, то вершины можно разбить на два множества, в одном - синие, в другом - красные, при этом внутри множества ребер между вершинами не будет по условию существования раскраски, поэтому граф будет двудольным.
+
 
+
2. Теорема Кенига гласит, что граф двудольный $\equiv$ все циклы в нем имеют четную длину. Доказательство приводить не буду, оно есть на wiki.
+
 
+
Получается, что
+
 
+
граф можно покрасить в 2 цвета $\equiv$ все циклы в нем имеют четную длину.
+
 
+
А теперь запускаем обход в глубину с произвольной вершины. Красим ее в синий, и переходим к ее соседям, которых красим в красный, и так далее, меняя используемый цвет на новой глубине. Если в графе есть циклы нечетной длины, то его нельзя покрасить в 2 цвета (доказано выше), и при обходе в глубину в какой-то момент мы у текущей вершины увидим уже покрашенного в такой же цвет соседа, то есть обнаружим, что есть цикл нечетной длины, и что нельзя такой граф покрасить в два цвета.
+
 
+
Пусть теперь в графе нет циклов нечетной длины. Покажем, что алгоритм обхода в глубину найдет способ покраски.
+
 
+
Результатом обхода графа в ширину является либо дерево, либо лес (если граф не связный). Пусть для определенности будет дерево. Вершины четной глубины в этом дереве покрасим одним цветом, вершины нечетной глубины  - другим. Покажем, что полученная раскраска - решение. Для этого надо показать, что в исходном графе нет ребер, у которых на концах вершины одного и того же цвета. Предположим, что в графе нашлось ребро, вершины которого имеют один и тот же цвет при полученной раскраске. Найдем в дереве эти вершины и проведем это ребро. У этих вершин в дереве есть общий предок, путь до него от каждой вершины имеет одну и ту же четность (потому что рассматриваемые вершины одного цвета). Получается, что в графе есть цикл нечетной длины (путь от одной вершины до общего предка + путь от общего предка до другой вершины + 1). Противоречие.
+
 
+
</m>
+

Версия 02:29, 26 декабря 2014

Полиномиальный алгоритм для раскраски графа в два цвета

Постройте полиномиальный алгоритм для раскраски графа в два цвета.