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