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

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

Определение и формализация

Формально, граф \( G = (V, E) \) называется двудольным, если существует такое разбиение множества вершин \( V \) на два подмножества \( V_1 \) и \( V_2 \) (доли), что \( V_1 \cup V_2 = V \), \( V_1 \cap V_2 = \varnothing \), и для любого ребра \( e = (u, v) \in E \) выполняется: \( u \in V_1, v \in V_2 \) (или наоборот). Доли часто обозначают как «левая» и «правая», хотя порядок не имеет значения. Если граф является двудольным, то разбиение может быть не единственным.

Двудольный граф обозначается как \( G = (V_1, V_2, E) \). Если \( |V_1| = m \) и \( |V_2| = n \), то такой граф называют \( (m, n) \)-двудольным. Полный двудольный граф, в котором каждая вершина первой доли соединена со всеми вершинами второй доли, обозначается \( K_{m,n} \).

Критерии двудольности

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

На практике двудольность графа можно проверить с помощью алгоритма раскраски в два цвета (обход в ширину или глубину). Алгоритм присваивает вершинам цвета (например, 0 и 1) по следующему правилу: стартовая вершина получает цвет 0, все её соседи — цвет 1, соседи соседей — снова 0 и так далее. Если в процессе обхода обнаруживается, что две смежные вершины имеют одинаковый цвет, то граф не является двудольным. Этот алгоритм работает за время \( O(|V| + |E|) \).

Свойства

• Отсутствие нечётных циклов: как указано выше, это необходимое и достаточное условие.
• Хроматическое число: двудольный граф является 2-раскрашиваемым, то есть его хроматическое число равно 2 (если граф не является пустым). Для пустого графа (без рёбер) хроматическое число равно 1.
• Совершенство: все двудольные графы являются совершенными графами.
• Максимальное количество рёбер: в двудольном графе с долями размером \( m \) и \( n \) максимальное количество рёбер равно \( m \cdot n \) (для полного двудольного графа \( K_{m,n} \)).
• Спектр: спектр матрицы смежности двудольного графа симметричен относительно нуля: если \( \lambda \) — собственное значение, то \( -\lambda \) — тоже собственное значение той же кратности.

Классификация и виды

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

Полный двудольный граф \( K_{m,n} \) — это граф, в котором каждая вершина первой доли соединена со всеми вершинами второй доли. Примеры: \( K_{1,3} \) (звезда), \( K_{2,2} \) (цикл из 4 вершин), \( K_{3,3} \) (граф, известный как «домики и колодцы» — классический пример не планарного графа).

Паросочетание

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

Двудольный двудольный граф (bipartite double cover)

Для любого графа (не обязательно двудольного) можно построить его двудольное двойное покрытие — двудольный граф, в котором каждая вершина исходного графа заменяется на две копии, а каждое ребро — на два ребра между соответствующими копиями.

Регулярный двудольный граф

Двудольный граф называется регулярным степени \( k \), если каждая вершина имеет степень \( k \). Примером является полный двудольный граф \( K_{k,k} \).

Применение

В информатике

• Задача о назначениях: поиск оптимального паросочетания во взвешенном двудольном графе (например, назначение работников на задачи). Решается с помощью венгерского алгоритма.
• Рекомендательные системы: пользователи и товары образуют двудольный граф, где ребро означает покупку или рейтинг. Алгоритмы коллаборативной фильтрации часто основаны на анализе такого графа.
• Сети и протоколы: двудольные графы используются для моделирования сетей с двумя типами узлов (например, коммутаторы и серверы).
• Теория кодирования: двудольные графы лежат в основе кодов с низкой плотностью проверок на чётность (LDPC-коды), используемых в современных системах связи (Wi-Fi, 5G, спутниковая связь).

В математике

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

В социологии и экономике

• Сети знакомств: моделирование отношений между двумя группами (например, мужчины и женщины на сайте знакомств, работодатели и соискатели).
• Анализ социальных сетей: двудольные графы используются для анализа сообществ, где есть два типа участников (например, пользователи и группы, авторы и статьи).

В биологии

• Экологические сети: моделирование взаимодействий между видами (например, опылители и растения, хищники и жертвы).
• Генетика: анализ взаимодействий между генами и белками.

Примеры

• Граф «звезда» \( K_{1,n} \): одна центральная вершина соединена с \( n \) листьями. Используется в моделировании сетей типа «звезда».
• Граф «цикл» чётной длины \( C_{2n} \): например, \( C_4 \) (квадрат) является двудольным, а \( C_3 \) (треугольник) — нет.
• Граф «решётка»: прямоугольная сетка, где вершины расположены в узлах, а рёбра — между соседними узлами. Решётка является двудольным графом, если раскрасить её в шахматном порядке.
• Граф «домики и колодцы» \( K_{3,3} \): полный двудольный граф с тремя вершинами в каждой доле. Известен тем, что не является планарным (его нельзя нарисовать на плоскости без пересечения рёбер).

Интересные факты

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

Источники

• Кёниг Д. Теория конечных и бесконечных графов. — М.: Гос. изд-во технико-теоретической литературы, 1936.
• Харари Ф. Теория графов. — М.: Мир, 1973.
• Дистель Р. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002.
• Ловас Л., Пламмер М. Прикладные задачи теории графов. — М.: Мир, 1998.
• Уилсон Р. Введение в теорию графов. — М.: Мир, 1977.