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

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

Двудольный граф (Bipartite graph) — граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Двудольные графы являются удобным средством графического представления отношений, а следовательно, и функций.

Bipartite graph.png

См. также

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.