Паросочетание
Материал из Algocode wiki
Версия от 16:38, 13 декабря 2019; Глеб (обсуждение | вклад) (Новая страница: «===Определение=== Паросочетание - набор ребер графа, такой, что каждой вершине инцидентно н...»)
Определение
Паросочетание - набор ребер графа, такой, что каждой вершине инцидентно не более одного ребра.
Как искать
Паросочетание в дереве можно искать ДП по поддеревьям, а в двудольном графе - Алгоритм Куна