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

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

Определение

Граф $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$ .

Применения

Сети Петри
Граф Леви
Теория кодирования
- Шаблон:Нп3
- Граф Таннера

См. также

Ссылки

Шаблон:Нет источников Шаблон:Навигация