Открыть главное меню
Двудольный граф

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

Содержание

ОпределениеПравить

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

Неориентированный граф   называется двудольным, если множество его вершин можно разбить на две части  , так, что

  • ни одна вершина в   не соединена с вершинами в   и
  • ни одна вершина в   не соединена с вершинами в  .

В этом случае, подмножества вершин   и   называются долями двудольного графа  .

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

Двудольный граф называется полным двудольным (это понятие отлично от полного графа; то есть, такого, в котором каждая пара вершин соединена ребром), если для каждой пары вершин   существует ребро  . Для

 

такой граф обозначается символом  .

ПримерыПравить

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

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

СвойстваПравить

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

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

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

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

ПримененияПравить

См. такжеПравить