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