Рубрики

Алгоритм Хопкрофта – Карпа для максимального соответствия | Комплект 1 (Введение)

Сопоставление в двудольном графе — это набор ребер, выбранных таким образом, что никакие два ребра не разделяют конечную точку. Максимальное соответствие — это соответствие максимального размера (максимальное количество ребер). При максимальном совпадении, если к нему добавлено какое-либо ребро, оно больше не совпадает. Для данного двудольного графа может быть более одного максимального соответствия.

Мы обсудили важность максимального соответствия и подход Форда Фулкерсона для максимального двустороннего соответствия в предыдущем посте . Временная сложность алгоритма на основе Форда Фулкерсона составляет O (V x E).

Алгоритм Хопкрофта Карпа — это усовершенствование, которое выполняется за время O (√V x E). Давайте определим несколько терминов, прежде чем мы обсудим алгоритм

Свободный узел или вершина. При наличии соответствующего M узел, который не является частью соответствия, называется свободным узлом. Изначально все вершины свободны (см. Первый график на диаграмме ниже). Во втором графике u2 и v2 свободны. В третьем графе ни одна вершина не является свободной.

Сопоставление и несоответствие ребер. При наличии соответствующего M ребра, являющиеся частью сопоставления, называются совпадающими ребрами, а ребра, которые не являются частью M (или соединяют свободные узлы), называются несоответствующими ребрами. В первом графе все ребра не совпадают. Во втором графе (u0, v1), (u1, v0) и (u3, v3) совпадают, а другие не совпадают.

Чередующиеся пути: При наличии совпадающего M, чередующийся путь — это путь, в котором ребра принадлежат альтернативно совпадающим и не совпадающим. Все пути с одним ребром являются чередующимися. Примерами чередующихся путей в среднем графе являются u0-v1-u2 и u2-v1-u0-v2.

Путь дополнения : при наличии соответствующего M, путь дополнения — это альтернативный путь, который начинается и заканчивается в свободных вершинах. Все пути с одним ребром, которые начинаются и заканчиваются свободными вершинами, являются увеличивающими путями. На диаграмме ниже пути расширения выделены синим цветом. Обратите внимание, что путь дополнения всегда имеет одно дополнительное совпадающее ребро.

Алгоритм Хопкрофта Карпа основан на концепции ниже.

Соответствие M не является максимальным, если существует путь расширения. Это также верно и для другого способа, т. Е. Совпадение является максимальным, если не существует пути расширения.

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

Алгоритм Хопкрофта Карпа

1) Initialize Maximal Matching M as empty.
2) While there exists an Augmenting Path p
     Remove matching edges of p from M and add not-matching edges of p to M
     (This increases size of M by 1 as p starts and ends with a free vertex)
3) Return M. 

Ниже приведена схема работы алгоритма.

В исходном графе все отдельные ребра увеличивают пути, и мы можем выбирать в любом порядке. На средней стадии есть только один путь расширения. Мы удаляем совпадающие ребра этого пути из M и добавляем несовпадающие ребра. В окончательном сопоставлении нет никаких дополнительных путей, поэтому сопоставление является максимальным.

Реализация алгоритма Хопкрофта Карпа обсуждается в наборе 2.

Алгоритм Хопкрофта – Карпа для максимального соответствия | Набор 2 (реализация)


Ссылки:

https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
http://www.dis.uniroma1.it/~leon/tcs/lecture2.pdf

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм Хопкрофта – Карпа для максимального соответствия | Комплект 1 (Введение)

0.00 (0%) 0 votes