Двудольный граф: как проверить раскраской в два цвета

Коротко

Что это такое

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

группа A:   1     2     3
            |\   /|    /
            | \ / |   /
            |  X  |  /
            | / \ | /
группа B:   4     5    6

Житейские примеры двудольных отношений:

• студенты и курсы (студент записан на курс);
• работники и вакансии (кандидат подходит на позицию);
• покупатели и товары (кто что купил);
• команды и матчи.

Общий признак — связи возникают между сущностями разных типов, а не внутри одного типа.

Критерий: нечётные циклы

Есть красивая теорема: граф двудолен тогда и только тогда, когда в нём нет циклов нечётной длины.

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

    1 (красный)
   / \
  /   \
2(син) — 3(?)

Вершина 3 соединена и с красной, и с синей. Третьего цвета нет — противоречие. Треугольник (цикл длины 3) не двудолен.

А цикл из четырёх вершин раскрашивается без проблем: красный, синий, красный, синий.

Отсюда практический способ проверки: пробуем раскрасить граф в два цвета. Получилось — двудолен, наткнулись на противоречие — нет.

Проверка через BFS

Идём в ширину, красим каждого соседа в противоположный цвет. Если встретили соседа того же цвета, что и текущая вершина, — нашли нечётный цикл.

from collections import deque


def is_bipartite_bfs(graph: dict) -> bool:
    color = {}      # вершина -> 0 или 1

    for start in graph:
        if start in color:
            continue          # уже обработана в другой компоненте

        color[start] = 0
        queue = deque([start])

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]   # противоположный
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False        # два соседа одного цвета

    return True


square = {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]}
triangle = {1: [2, 3], 2: [1, 3], 3: [1, 2]}

print(is_bipartite_bfs(square))    # True  — цикл длины 4
print(is_bipartite_bfs(triangle))  # False — цикл длины 3

Внешний цикл по всем вершинам обязателен. Граф может быть несвязным, и одного запуска BFS не хватит — часть компонент останется непроверенной. Это самая частая ошибка в этой задаче.

Трюк 1 - color[node] даёт противоположный цвет: 0 превращается в 1 и наоборот. Альтернатива — color[node] ^ 1.

Проверка через DFS

Тот же алгоритм рекурсивно. Иногда короче, но помните про глубину стека на больших графах.

def is_bipartite_dfs(graph: dict) -> bool:
    color = {}

    def dfs(node: int, c: int) -> bool:
        color[node] = c

        for neighbor in graph[node]:
            if neighbor not in color:
                if not dfs(neighbor, 1 - c):
                    return False
            elif color[neighbor] == c:
                return False

        return True

    return all(dfs(v, 0) for v in graph if v not in color)

Обе версии работают за O(V + E) — каждая вершина и каждое ребро просматриваются один раз.

Как получить сами доли

Часто нужна не только проверка, но и само разбиение. Достаточно вернуть словарь цветов:

def bipartition(graph: dict):
    color = {}
    # ... тот же код раскраски ...

    part_a = [v for v, c in color.items() if c == 0]
    part_b = [v for v, c in color.items() if c == 1]
    return part_a, part_b

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

Зачем это нужно: паросочетания

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

Реальные постановки:

• распределить работников по задачам, учитывая кто что умеет;
• расселить студентов по комнатам;
• назначить водителей на маршруты;
• составить расписание, где преподаватели не пересекаются по аудиториям.

Для двудольных графов эта задача решается за полиномиальное время алгоритмом Куна (венгерским алгоритмом) или через максимальный поток. Для произвольных графов она гораздо сложнее — нужен алгоритм Эдмондса с «цветками».

Именно поэтому проверка двудольности — не абстрактное упражнение: она определяет, какой инструмент применим к вашей задаче.

Ещё несколько применений

Проверка корректности расписания. Если конфликты образуют нечётный цикл, развести участников на две смены невозможно.

Двухцветная раскраска карты. Регионы можно покрасить в два цвета без совпадений у соседей ровно тогда, когда граф смежности двудолен.

Обнаружение противоречий. Задачи вида «эти двое должны быть в разных командах» сводятся к двудольности: если решения нет, значит в ограничениях противоречие.

Частые ошибки

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

Использование visited вместо color. Нужно хранить именно цвет, а не факт посещения: без цвета нечего сравнивать.

Проверка цвета до присвоения. Порядок в BFS важен: сначала проверяем, есть ли сосед в словаре, и только потом сравниваем цвета.

Ориентированный граф. Понятие двудольности определено для неориентированных графов. Для ориентированного нужно рассматривать его неориентированную версию.

Что запомнить

• Двудольный граф — вершины делятся на две группы, рёбра идут только между группами.
• Граф двудолен тогда и только тогда, когда в нём нет циклов нечётной длины.
• Проверка — раскраска в два цвета обходом в ширину или глубину, O(V + E).
• Обязательно обходите все компоненты, а не только одну.
• Двудольность открывает доступ к эффективным алгоритмам паросочетаний.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→