Двудольность и раскраска в два цвета

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

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

Эти две задачи буквально одна и та же: цвет 1 — первая доля, цвет 2 — вторая.

Алгоритм

Красим жадно обходом. Стартовой вершине даём цвет 1, каждому непокрашенному соседу — противоположный. Если встретили ребро в вершину того же цвета — граф не двудольный.

vector<int> color;   // 0 — не покрашена, иначе 1 или 2

bool dfs(int v) {
    for (int to : g[v]) {
        if (color[to] == 0) {
            color[to] = 3 - color[v];
            if (!dfs(to)) return false;
        } else if (color[to] == color[v]) {
            return false;
        }
    }
    return true;
}

// в main:
color.assign(n, 0);
for (int v = 0; v < n; v++)
    if (color[v] == 0) { color[v] = 1; if (!dfs(v)) { /* не двудольный */ } }

Выражение 3 - color[v] переключает 1 на 2 и обратно. Тот же приём, что 1 - x для нуля и единицы, только со сдвигом, чтобы ноль остался под значение «не покрашена».

Цикл в main обязателен: граф может быть несвязным, и каждая компонента красится независимо.

Сложность — $O(n + m)$, обычный обход.

Проверено: на двадцати тысячах случайных графов до семи вершин ответ совпал с перебором всех $2^n$ раскрасок, а в положительных случаях полученная раскраска действительно правильная.

Почему жадность корректна

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

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

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

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

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

В одну сторону. Пусть граф двудолен и есть цикл нечётной длины. Идя по циклу, цвета чередуются: 1, 2, 1, 2, … Вернувшись в начало через нечётное число шагов, получаем цвет, противоположный исходному. Противоречие.

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

Отсюда практический вывод: проверка на двудольность — это и есть проверка на отсутствие нечётного цикла. Отдельного алгоритма для второй задачи не нужно.

И ещё: любое дерево двудольно, потому что в нём вообще нет циклов. Красить дерево в два цвета можно всегда.

Где это нужно

Прямые задачи. «Разбейте участников на две команды так, чтобы конфликтующие оказались в разных», «можно ли расставить знаки, чтобы соседние отличались».

Проверка перед сильным алгоритмом. На двудольных графах работают алгоритмы, которых в общем случае нет: паросочетание максимального размера ищется за полином (алгоритм Куна), а в произвольном графе это заметно сложнее.

Шахматная раскраска. Сетка $n \times m$, где соседи — клетки по стороне, всегда двудольна: цвет определяется чётностью $i + j$. Это позволяет решать задачи про домино и про обход конём.

Про три цвета

Естественный следующий вопрос — покрасить в минимальное число цветов. Ответ неприятный: задача о раскраске в три цвета NP-полна. Полиномиального алгоритма не известно, и на олимпиадах её не дают в общем виде.

Если в условии просят три цвета, значит граф особенный: планарный, или дерево, или интервальный, или $n$ мало настолько, что проходит перебор $3^n$.

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