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

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

• ни одна вершина в ${\displaystyle U}$ не соединена с вершинами в ${\displaystyle U}$
• ни одна вершина в ${\displaystyle V}$ не соединена с вершинами в ${\displaystyle V}$

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

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

${\displaystyle |U|=i,|V|=j}$

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

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

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

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

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

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

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