Паросочетание

Материал из Algocode wiki
Версия от 16:38, 13 декабря 2019; Глеб (обсуждение | вклад) (Новая страница: «===Определение=== Паросочетание - набор ребер графа, такой, что каждой вершине инцидентно н...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определение

Паросочетание - набор ребер графа, такой, что каждой вершине инцидентно не более одного ребра.

Как искать

Паросочетание в дереве можно искать ДП по поддеревьям, а в двудольном графе - Алгоритм Куна

Источник — http://wiki.algocode.ru/index.php?title=Паросочетание&oldid=944