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

Определение

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

Как искать

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