Метод увеличивающих путей

Пусть G – граф, М – некоторое паросочетание в нем. Ребра паросочетания будем называть сильными, остальные ребра графа – слабыми. Вершину назовем свободной, если она не принадлежит ребру паросочетания. Чередующимся путем относительно данного паросочетания называется простой путь, в котором чередуются сильные и слабые ребра (т.е. за сильным ребром следует слабое, за слабым – сильное). Чередующийся путь называется увеличивающим путем, если он соединяет две свободные вершины. Если имеется увеличивающий путь относительно данного паросочетания, то можно построить большее паросочетание – нужно вдоль этого пути превратить слабые ребра в сильные, а сильные в слабые. Эту операцию назовем инверсией. В результате инверсии мощность паросочетания увеличивается на 1.

Теорема об увеличивающем пути. Паросочетание является наибольшим тогда и только тогда, когда относительно него нет увеличивающих путей.

Для решения задачи о паросочетании остается научиться находить увеличивающие пути или убеждаться, что таких путей нет. Это можно сделать, перебирая чередующиеся пути (подобно перебору путей при поиске гамильтонова цикла). Дело осложняется тем, что чередующихся путей может быть много (см. задачу 7.4). Оказывается, нет необходимости перебирать их все. Известны эффективные алгоритмы, которые ищут увеличивающие пути для произвольных графов. Рассмотрим простой алгоритм, решающий эту задачу для двудольных графов.