🔀 Дискретка

Двудольный граф

англ. Bipartite graph

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

Двудольный граф — граф, вершины которого разбиваются на два непересекающихся множества (доли) так, что каждое ребро соединяет вершины из разных долей; рёбер внутри одной доли нет. Картинка из жизни: слева задачи, справа исполнители, рёбра — кто что умеет. Полный двудольный граф $K_{m, n}$ соединяет каждую вершину первой доли с каждой вершиной второй; в нём ровно $mn$ рёбер и $m + n$ вершин. Частный случай — дерево: циклов в нём нет вообще, а значит, нет и нечётных, поэтому любое дерево двудольно.

Интуиция — раскраска в два цвета. Двудольность означает, что вершины можно покрасить в два цвета так, чтобы соседние различались: соседи всегда из другой доли. Отсюда главный критерий — теорема Кёнига: граф двудолен тогда и только тогда, когда в нём нет циклов нечётной длины. Чётный цикл красится чередованием цветов без проблем; нечётный — в принципе нет: замыкаясь, чередование упирается в конфликт. Алгоритм проверки — обход в ширину: стартовую вершину красим в цвет 1, соседей — в цвет 2 и так далее; встретили ребро между одинаково окрашенными — граф не двудолен. Если циклы и пары вершин уже знакомы по хроматическому числу, двудольность — просто случай $χ \leq 2$ .

G двудолен ⟺ нет циклов нечётной длины (Кёниг); ∣ E (K_{m, n}) ∣ = m \cdot n; G двудолен \Rightarrow χ (G) \leq 2

критерий Кёнига, число рёбер полного двудольного графа и следствие для раскраски: двудольный граф красится ровно в два цвета (при наличии хоть одного ребра)

Микропример: $K_{3, 3}$ — три вершины слева, три справа, все $3 \cdot 3 = 9$ рёбер между долями и ни одного внутри; кратчайший цикл в нём имеет длину $4$ — треугольника быть не может, для него нужно ребро внутри доли. Шестиугольник $C_{6}$ двудолен: доли чередуются через вершину; пятиугольник $C_{5}$ — нет, нечётный цикл. Где встречается: расписания (занятия и аудитории, преподаватели и пары), паросочетания — выбор рёбер без общих вершин (максимум назначений ищется алгоритмом Куна), проверка планарности — $K_{3, 3}$ вместе с $K_{5}$ запрещён теоремой Куратовского: нарисовать его без пересечений рёбер невозможно.

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

Проверка двудольности и ловушки

Алгоритм за один обход: BFS-раскраска двумя цветами по всем компонентам; конфликт одинаково окрашенных соседей — не двудолен. Ловушки: «нет нечётных циклов» — это сильнее, чем «нет циклов» (цикл длины 4 или 6 двудольность не рушит); несвязный граф проверяется покомпонентно, каждая доля собирается по всей компоненте;

K_{3, 3}

— канонический непланарный двудольный граф, «пересечения рёбер» и «двудольность» никак не связаны.

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

Почему любое дерево двудольно?

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

Что такое паросочетание и зачем тут двудольность?

Паросочетание — набор рёбер без общих вершин; в двудольном графе это назначение «задачи — исполнители»: выбранные рёбра говорят, кто что получил. Максимальное паросочетание ищется увеличивающими путями (алгоритм Куна), а теорема Холла отвечает на вопрос «покроет ли назначение всю долю»: у каждого подмножества задач должно быть не меньше соседей, чем самих задач.