Нахождение максимального паросочетания:          

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

 

Hosted by uCoz