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

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

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

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

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

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

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

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

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

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

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

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

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