Двудо́льный граф или бигра́ф в теории графов — это граф, вершины которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной другой части. То есть, между вершинами одной и той же части рёбра отсутствуют.
Определение
Граф называется двудольным, если множество его вершин можно разбить на две части так, что: ни одна вершина в не соединена с вершинами в ; ни одна вершина в не соединена с вершинами в .
В этом случае, подмножества вершин и называются долями двудольного графа .
Связанные определения Двудольный граф называется полным двудольным (это понятие отлично от полного графа; то есть, такого, в котором каждая пара вершин соединена ребром), если для каждой пары вершин существует ребро . Для
такой граф обозначается символом .
Примеры Примеры двудольных графов: любое дерево является двудольным графом; любой простой цикл, состоящий из чётного числа вершин; любой планарный граф, у которого каждая грань ограничена чётным количеством ребер.
Двудольные графы естественно возникают при моделировании отношений между двумя различными классами объектов. К примеру граф футболистов и клубов: ребро соединяет соответствующего игрока и клуб, если игрок играл в этом клубе.
Двудольные графы используют для описания LDPC-кодов.
Свойства Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины. В частности двудольный граф не может содержать клику размером более 2. Граф является двудольным тогда и только тогда, когда он 2-хроматический; то есть его хроматическое число равняется двум. Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые элементов одной из долей связаны по крайней мере с элементами другой (Теорема о свадьбах). Полный двудольный граф, у которого в каждой части больше 2 вершин, является непланарным. Любой двудольный граф является совершенным.
Проверка двудольности
Чтобы проверить граф на двудольность, в каждом компоненте связности нужно выбрать любую вершину и помечать остальные вершины при обходе графа (например, поиском в ширину) поочерёдно как четные и нечетные (см. иллюстрацию). Если конфликты не возникают, то четные вершины образуют множество , а нечётные — множество .
Применения Сети Петри Граф Леви Теория кодирования
Граф Таннера
См. также Словарь терминов теории графов Биекция Многодольный граф Квазидвудольный граф
Ссылки
Information System on Graph Classes and their Inclusions: bipartite graph
Bipartite graphs in systems biology and medicine
Категория:Семейства графов *