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

Биграф

Двудольный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

Определение

Полный двудольный граф $K_{3,2}$

Неориентированный граф $G = (W,E)$ называется двудольным, если множество его вершин можно разбить на две части $U \cup V = W$, $|U|>0$, $|V|>0$, так, что

• ни одна вершина в $U$ не соединена с вершинами в $U$ и
• ни одна вершина в $V$ не соединена с вершинами в $V$

Двудольный граф называется полным, если для каждой пары вершин $u \in U, v \in V$ существует ребро $(u,v) \in E$. Для

$|U|=i, |V|=j$

такой граф называется $K_{i, j}$

Примеры

Двудольные графы естественно возникают при моделировании отношений между двумя различными классами объектов. К примеру граф футболистов и клубов, ребро соединяет соответствующего игрока и клуб, если игрок играл в этом клубе. Более абстрактные примеры двудольных графов:

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

Свойства

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

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

Проверка двудольности с помощью чётности расстояний

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

Применения

• Сети Петри
• Граф Леви
• Теория кодирования
  • Factor graph
  • Tanner graph

См. также

• Словарь терминов теории графов
• Биекция

Ссылки

Видеозапись лекции о двудольных графах, Эйлеровых и Гамильтоновых путях