Двудольные графы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Двудольные графы)
(Двудольные графы)
 
Строка 1: Строка 1:
=== Двудольные графы ===
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=

Текущая версия на 22:42, 22 ноября 2016

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


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