Двудольность: когда вершины делятся на две команды

Если ты знаешь определение двудольности, умеешь проверять её обходом за O(V + E) и помнишь критерий «нет нечётных циклов», листай до «Теперь сам».

Как думаешь, что мешает разделить на две команды

Есть компания людей, некоторые друг с другом в ссоре. Надо рассадить их за два стола так, чтобы поссорившиеся оказались за разными. Прежде чем читать дальше, придумай самую маленькую компанию, в которой это НЕВОЗМОЖНО. Сколько в ней человек и как устроены ссоры?

На что это похоже

Шахматная доска. Покрась клетки в два цвета по правилу «соседние - разного цвета»; получится привычная шахматная раскраска, и она существует, потому что любой замкнутый маршрут по клеткам имеет чётную длину. А теперь представь доску, где три клетки попарно соседние, - такую раскрасить двумя цветами нельзя, как ни старайся: третья клетка обязательно совпадёт по цвету с одной из первых двух.

Механизм: красим обходом

color = [-1] * V                 # -1 не покрашена, 0 и 1 - две доли

def bipartite():
    for s in range(V):
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for u in adj[v]:
                if color[u] == -1:
                    color[u] = 1 - color[v]      # противоположный цвет
                    q.append(u)
                elif color[u] == color[v]:
                    return False                 # ребро внутри доли
    return True

Три замечания к коду. Первое: обход годится любой - в ширину или в глубину, разницы нет, красим мы при первом посещении. Второе: внешний цикл обязателен - граф может быть несвязным, и каждую компоненту красят независимо (её стартовую вершину можно класть в любую долю). Третье: конфликт ищется на РЁБРАХ, а не на вершинах: пока не наткнулись на ребро между одноцветными, всё в порядке.

Правило

Граф двудолен, если вершины делятся на две группы без рёбер внутри группы; это равносильно правильной раскраске в два цвета. Проверяется обходом за O(V + E): красим стартовую вершину, соседей - в противоположный цвет, и ищем ребро между одноцветными. Каждую компоненту красят независимо. Точный критерий: граф двудолен ⇔ в нём НЕТ циклов нечётной длины. Деревья и леса двудольны всегда, треугольник - никогда.

Разбор: почему мешают именно нечётные циклы

Докажем в обе стороны - это короткое и красивое рассуждение.

Если граф двудолен, нечётных циклов нет. Пусть есть цикл v₁ → v₂ → ... → v_k → v₁. Цвета по рёбрам чередуются: v₁ в доле 0, v₂ в доле 1, v₃ снова в 0 и так далее. Значит цвет вершины v_i определяется чётностью i. Чтобы цикл замкнулся, v_k должна быть противоположного цвета относительно v₁, то есть k должно быть чётным. Нечётный цикл замкнуться не может.

Если нечётных циклов нет, граф двудолен. Раскрасим так: возьмём в каждой компоненте стартовую вершину s и покрасим вершину v в цвет расстояние(s, v) mod 2. Покажем, что это правильная раскраска. Пусть нашлось ребро u-v между вершинами одного цвета, то есть расстояния до них имеют одинаковую чётность. Тогда путь от s до u, ребро u-v и путь от v обратно к s образуют замкнутый маршрут длины d(u) + 1 + d(v) - а это число НЕЧЁТНО (сумма двух чисел одной чётности плюс единица). Замкнутый маршрут нечётной длины обязательно содержит нечётный цикл (общие куски путей проходятся дважды и дают чётный вклад, который можно выбросить). Противоречие с условием.

Отсюда и практический бонус алгоритма: когда обход находит конфликтное ребро, он не просто говорит «не двудолен» - по дереву обхода легко восстановить сам нечётный цикл и показать его человеку как доказательство. В задачах про конфликты это ровно то объяснение, которое нужно: «вот три условия, которые невозможно удовлетворить одновременно».

Разбор: проверяем граф руками

Граф: 1-2, 2-3, 3-4, 4-1, 1-3. Начинаем с вершины 1, обход в ширину.

1. color[1] = 0. Очередь: [1].
2. Достаём 1. Соседи: 2, 4, 3. Все не покрашены → color[2] = color[4] = color[3] = 1. Очередь: [2, 4, 3].
3. Достаём 2. Соседи: 1 (цвет 0, отличается - хорошо), 3 (цвет 1, а у самой двойки цвет 1) - конфликт, граф не двудолен.

Где именно спрятался нечётный цикл? В треугольнике 1-2-3-1: рёбра 1-2, 2-3 и 1-3 есть, длина цикла три. Заметь, что квадрат 1-2-3-4-1 сам по себе был бы двудольным - проблему создало «диагональное» ребро 1-3.

Что ломается без этого

Первое: забыть внешний цикл и проверить только компоненту стартовой вершины - несвязный граф с треугольником во второй компоненте будет объявлен двудольным. Второе: сравнивать цвета вершин, а не концов ребра: двудольность нарушает именно ребро, и находить его надо при просмотре списков смежности. Третье: считать, что двудольность связана с чётностью числа вершин или рёбер - не связана вовсе: путь из трёх вершин двудолен, треугольник из трёх - нет. Четвёртое: применять проверку к ориентированному графу, забыв, что направления здесь не играют роли: для двудольности граф рассматривают как неориентированный. Пятое: думать, что раскраска единственна - в связной компоненте она единственна с точностью до обмена цветов, а в несвязном графе каждую компоненту можно переворачивать независимо, так что вариантов 2^(число компонент).

Зачем это в работе

Двудольность - первый вопрос в целом классе задач «разделить на два» и «сопоставить одно другому». Распределение задач по двум ресурсам, разделение процессов на два узла так, чтобы конфликтующие не встретились, проверка схемы на возможность развести в два слоя. Но главное применение - вход в теорию ПАРОСОЧЕТАНИЙ: задачи «назначить работников на работы», «студентов на проекты», «водителей на маршруты» формулируются как поиск максимального паросочетания в двудольном графе, и там есть быстрые алгоритмы - но сперва граф должен быть двудольным, а это как раз проверяется обходом. Ещё пример из практики: проверка непротиворечивости системы ограничений вида «эти двое должны быть по разные стороны» - конфликт находится вместе с нечётным циклом, который можно показать как объяснение. И заметь общий мотив главы: двудольность - это раскраска в ДВА цвета, и она решается за линейное время, а уже для трёх цветов задача становится вычислительно трудной. Разница между двумя и тремя здесь принципиальная - об этом следующий урок.

Теперь сам

Граф: 1-2, 2-3, 3-4, 4-5, 5-1. Двудолен ли он? А если добавить ребро 1-3?