Задача о нахождении максимального паросочетания в
двудольном графе звучит
следующим образом: Из имеющихся ребер, соединяющих доли графа нужно выбрать
несколько так, чтобы каждая вершина имела не более одного прмеченного
входящего/выходящего ребра и колличество их было максимально.
Алгоритм:
1) Для начала построим первое решение жадным алгоритмом.(Это не обезательно.
Лишь для повышения скорости)
2) Найдем путь из одной доли в другую, начинающийся и заканчивающийся
невыделенным ребром, причем в этом пути выделенные и невыделенные ребра
должны чередоваться.
3) Изменим раскраску ребер на этом пути на противоположную - те ребра,
которые были не отмечны, отмечаем и наоборот
4) Повторяем с п.2), пока находится путь.
Сложность алгоритма, при использовании очереди для поиска пути - О(N^3)
|