Задача о максимальномпаросочетании. Волновой алгоритм

 

Паросочетание – подмножество попарно несмежных ребер.

Задача нахождения максимального подмножества таких ребер и называется задача о максимальномпаросочетании. (Например, задача о трудоустройстве)

Полным паросочетанием называется паросочетание, в котором участвуют все вершины графа.

 

«алгоритм чередующихся цепей»

Пусть М – паросочетание в графе G, вершина v–парная, если она инцидентна ребру, принадлежащему M.

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

1)

2) найти чередующуюся цепь Ротн. М

3) если цепь найдена, увеличить паросочетание М вдоль цепи Р и перейти к шагу 2. Иначе конец алгоритма.

Корректность алгоритма доказывается теоремой Бержа:

Паросочетание М является маквсимальным тогда и только тогда, когда в графе нет чередующихся цепей относительно М.

 

Для нахождения чередующейся цепи используется волновой алгоритм:

V₁, v₂ – доли в графе

Пусть имеется паросочетание М; F₀, F₁,... –волны алгоритма (подмножества вершин)

1) в множество F₀включаем все непарные вершины из v₁

2) цикл по k=1,...

Если k нечетное,

то в F_kвключаются

иначе в F_kвключаются

конец если

если в F_kвходит непарная вершина,

то конец алгоритма, чередующаяся цепь найдена,

конец если

если F_k= , то конец алгоритма, чередующаяся цепь не найдена

конец цикла

 

Пример:

1-a - чередующаяся цепь

2-c

3-b

4-e

 

5-c-2-a-1-d - ОТВЕТ

5-e-4-b-3