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

Материал из Викиконспекты
Версия от 22:15, 22 ноября 2016; 188.227.78.144 (обсуждение) (Двудольные графы)
Перейти к: навигация, поиск

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

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


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