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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Биграф

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

Определение[править | править исходный текст]

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

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

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

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

|U|=i, |V|=j

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

Примеры[править | править исходный текст]

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

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

Свойства[править | править исходный текст]

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

Проверка двудольности[править | править исходный текст]

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

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

Применения[править | править исходный текст]

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Видеозапись лекции о двудольных графах, Эйлеровых и Гамильтоновых путях