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

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

Определение[править]

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

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

В этом случае, подмножества вершин $U$ и $V$ называются долями двудольного графа $G$ .

Связанные определения[править]

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

| U | = i, | V | = j

такой граф обозначается символом $K_{i, j}$ .

Примеры[править]

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

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

Двудольные графы используют для описания LDPC кодов.

Свойства[править]

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

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

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

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