WikiSort.ru - Не сортированное

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

Определение

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

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

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

Примеры

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

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

Свойства

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

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

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

Применения

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

См. также

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

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 19 января 2013 года.

	Двудольный граф на Викискладе