To:
-dila-Цитата(AlgoList)
Паросочетанием называется множество попарно несмежных ребер (не имеющих общих вершин). Паросочетание называется совершенным, если оно покрывает все вершины. Весом паросочетания называется суммарный вес входящих в него ребер
Искать максимальное паросочетание можно, например,
Алгоритмом Куна