Паросочетание – подмножество попарно несмежных ребер.
Задача нахождения максимального подмножества таких ребер и называется задача о максимальномпаросочетании. (Например, задача о трудоустройстве)
Полным паросочетанием называется паросочетание, в котором участвуют все вершины графа.
«алгоритм чередующихся цепей»
Пусть М – паросочетание в графе G, вершина v–парная, если она инцидентна ребру, принадлежащему M.
Путь, соединяющий две непарные вершины, в котором чередуются ребра, входящие и не входящие в М, называется чередующейся цепью относительно М.
1)
2) найти чередующуюся цепь Ротн. М
3) если цепь найдена, увеличить паросочетание М вдоль цепи Р и перейти к шагу 2. Иначе конец алгоритма.
Корректность алгоритма доказывается теоремой Бержа:
Паросочетание М является маквсимальным тогда и только тогда, когда в графе нет чередующихся цепей относительно М.
Для нахождения чередующейся цепи используется волновой алгоритм:
V1, v2 – доли в графе
Пусть имеется паросочетание М; F0, F1,... –волны алгоритма (подмножества вершин)
|
|
1) в множество F0включаем все непарные вершины из v1
2) цикл по k=1,...
Если k нечетное,
то в Fkвключаются
иначе в Fkвключаются
конец если
если в Fkвходит непарная вершина,
то конец алгоритма, чередующаяся цепь найдена,
конец если
если Fk= , то конец алгоритма, чередующаяся цепь не найдена
конец цикла
Пример:
1-a - чередующаяся цепь
2-c
3-b
4-e
5-c-2-a-1-d - ОТВЕТ
5-e-4-b-3