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

Материал из Викиконспекты
Версия от 22:42, 22 ноября 2016; 188.227.78.144 (обсуждение) (Двудольные графы)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Определение:
Двудольный граф или биграф (англ. bipartite graph) — граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части. Двудольный граф с [math]n[/math] вершинами в одной доле и [math]m[/math] во второй обозначается [math]K_{n,m}[/math].


Пример двудольного графа