Правильное паросочетание

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

Правильное паросочетание (Proper matching) — частичное паросочетание \,\{A,M_{A}\} в двудольном графе \,(V,V';E) такое, что после удаления всех вершин из \,V и \,V', которые участвуют в \,M_{A} и всех ребер с концом в этих вершинах остающееся множество V \setminus A является множеством без дефицита (или с дефицитом, равным нулю) в полученном графе.

Литература

  • Оре О. Теория графов. — М.: Наука, 1968.