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

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


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