Биграф

Материал из Википедии — свободной энциклопедии

Черновик [показать страницу] (сравнить)

Данная версия статьи не досматривалась участниками с соответствующими правами. Вы можете прочитать последнюю досмотренную версию от 10 мая 2009, однако она может значительно отличаться от текущей версии. Проверки требуют 3 правки.

Перейти к: навигация, поиск

Биграф

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

Содержание

1 Определение
2 Свойства
3 Проверка двудольности
- 3.1 Алгоритм Хопкрофта — Карпа
4 Применения
5 См. также

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

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

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$ .