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

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

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

Определение

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

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

• ни одна вершина в [math]\displaystyle{ U }[/math] не соединена с вершинами в [math]\displaystyle{ U }[/math]
• ни одна вершина в [math]\displaystyle{ V }[/math] не соединена с вершинами в [math]\displaystyle{ V }[/math]

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

Связанные определения

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

[math]\displaystyle{ |U|=i, |V|=j }[/math]

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

Примеры

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

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

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

Свойства

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

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

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

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

Применения

• Сети Петри
• Граф Леви
• Теория кодирования
  • 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