16. Паросочетания в двудольных графах

Паросочетанием в графе называется множество попарно несмежных ребер.

Паросочетание M называется совершенным, если каждая вершина графа является концом какого-то ребра из M.

Пусть A – подмножество вершин графа G=(V,E). Определим N(A) как множество вершин из V\A, смежных хотя бы с одной вершиной из A.

Теорема Холла. Пусть G – двудольный граф, X и Y – его доли. Тогда в G существует совершенное паросочетание если и только если для любого подмножества AÍ X , |A|£|N(A)|

Задача о наибольшем паросочетании

Вход: двудольный граф G с долями X и Y.

Найти: наибольшее паросочетание M в графе G.

Если |X| = |Y| = |M|, то M будет соверешнным паросочетанием . Пусть M – какое-то паросочетание в графе G. Вершины, инцидентные ребрам из M, назовем насыщенными.

Цепь, ребра которой поочередно входят и не входят в M, назовем чередующейся

относительно M. Чередующуюся цепь, у которой концы являются ненасыщенными вершинами, назовем увеличивающей.

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

Алгоритм построения наибольшего паросочетания.

1. Взять какое-то начальное паросочетание M.

2. Попытаться найти увеличивающую относительно M цепь.

3. Если такой цепи нет, то M – наибольшее паросочетание.

4. Если такая цепь нашлась, то построить с ее помощью новое паросочетание M большего размера и перейти в 2.

Как найти увеличивающую цепь?

Орграф – это граф, у которого на каждом ребре

задана ориентация .

Орграф – это пара (V,A), где V – конечное множество,

а AÍV² .

Из вершины u в вершину v в орграфе существует путь

тогда и только тогда, когда v получила метку в результате выполнения поиска в ширину с начальной вершиной u .