Двудольный граф (теория графов)

Биграф

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

Определение

Полный двудольный граф 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 элементами другой (Теорема Холла).

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

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

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

Алгоритм Хопкрофта — Карпа

Применения

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

См. также

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