Информатика · объяснение и практика

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

Раскрасьте граф двумя цветами по соседям, найдите конфликт на нечётном цикле и проверьте каждую компоненту вместо одной красивой части рисунка.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

В двудольном неориентированном графе вершины разделяются на две группы, а каждое ребро соединяет разные группы. Это равносильно корректной раскраске двумя цветами. Нечётный цикл делает такую раскраску невозможной, поскольку при чередовании цветов конец цикла конфликтует с началом.

Цвет назначают по связям, а не по расположению

Четыре вершины А, Б, В и Г соединены в квадрат без диагоналей. Назначим А синий цвет. Тогда Б и Г должны быть оранжевыми, а В — синим. Все четыре ребра соединяют разные цвета. На рисунке вершины могут стоять в любых местах: левый и правый края листа не обязаны совпадать с долями графа.

Добавим диагональ А—В. Её концы уже одного цвета, и появляется треугольник А—Б—В—А. Перекрасить только В нельзя: это нарушит соседние рёбра. Перестановка названий цветов во всей компоненте также не поможет. Проблема заключается в структуре нечётного цикла, а не в первоначальном выборе синего цвета.

Почему цикл чётной длины замыкается правильно

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

Для проверки можно использовать очередь или стек. Нераскрашенной вершине назначают первый цвет, её соседям противоположный, затем продолжают обход. Если у уже раскрашенного соседа цвет совпал с текущим, найден конфликт. Когда одна компонента закончилась, запускают обход из следующей нераскрашенной вершины: граф может состоять из нескольких частей.

Пример

Граф содержит отдельный квадрат и отдельный треугольник. Достаточно ли раскраски квадрата для общего ответа?

Нет. Квадрат раскрашивается, но треугольник — нечётный цикл. Для двудольности всего графа требуется успешная проверка каждой компоненты; один конфликт уже опровергает общий результат.

Не путайте двудольность с полнотой связей

В двудольном графе не обязательно есть ребро между каждой парой из разных групп. Полный двудольный граф — отдельный частный случай, где присутствуют все такие связи. Списки «ученики» и «проекты» с отмеченными назначениями дают двудольную модель даже тогда, когда большинство возможных назначений не выбрано.

Изолированную вершину можно поместить в любую долю; она не создаёт ограничений на соседей. Петля, наоборот, соединяет вершину с самой собой и требует двух разных цветов у одного объекта, поэтому исключает двудольность. Эти случаи полезно проверить до сложного обхода. Результат описывает допустимость разделения по рёбрам, а не число найденных пар или качество назначения.

От чтения к действию

А теперь — вы

Одна компонента — цикл из шести вершин без дополнительных рёбер. Можно ли раскрасить его двумя цветами?

Частые вопросы

Любой граф с циклом не является двудольным?

Нет. Препятствие — нечётный цикл. Квадрат без диагоналей имеет цикл, но корректно раскрашивается двумя цветами.

Доли должны содержать одинаковое число вершин?

Нет. Определение запрещает рёбра внутри доли, но не требует равенства размеров двух групп.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться