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

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

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

Определение

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

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

Применения

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

См. также

• Словарь терминов теории графов
• Биекция
• Многодольный граф
• Квазидвудольный граф

Ссылки

• Hazewinkel, Michiel, ed. (2001), "Graph, bipartite", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Information System on Graph Classes and their Inclusions: bipartite graph
• Weisstein, Eric W. Bipartite Graph (англ.) на сайте Wolfram MathWorld.
• Bipartite graphs in systems biology and medicine