Чётный граф (теория графов)
- Чётный граф (теория графов)
-
Биграф
Биграф, двудольный граф или чётный граф — это математический термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества U и V, то связи будут только между вершинами из разных подмножеств.
Определение
Полный двудольный граф K3,2
Неориентированный граф G = (W,E) называется двудольным, если множество его вершин можно разбить на две части
, | U | > 0, | V | > 0, так, что
- ни одна вершина в U не соединена с вершинами в U и
- ни одна вершина в V не соединена с вершинами в V
Двудольный граф называется полным, если для каждой пары вершин
существует ребро
. Для
- | U | = i, | V | = j
такой граф называется Ki,j
Свойства
- Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины. Поэтому двудольный граф не может содержать клику размером более 2.
- Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем (то есть его хроматическое число равняется двум)
- Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые k элементов одной из долей связаны по крайней мере с k элементами другой (Теорема Холла).
Проверка двудольности
Проверка двудольности с помощью чётности расстояний
Для того, чтобы проверить граф на предмет двудольности, достаточно в каждой компоненте связности выбрать случайно одну вершину и помечать оставшиеся вершины во время поиска в глубину поочерёдно как чётные и нечётные (см. иллюстрацию). Если при этом не возникнет конфликта, все чётные вершины образовывают множество U, а все нечётные — V.
Алгоритм Хопкрофта — Карпа
Применения
- Сети Петри
- Граф Леви
- Теория кодирования
- Factor graph
- Tanner graph
См. также
Wikimedia Foundation.
2010.
Полезное
Смотреть что такое "Чётный граф (теория графов)" в других словарях:
Двудольный граф (теория графов) — Биграф Биграф, двудольный граф или чётный граф это математический термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества U и V, то связи будут… … Википедия
Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Инцидентность — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Подграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия