Максимально подходящий край - Maximally-matchable edge

В теория графов, а максимально совместимый край в графе - это ребро, которое входит хотя бы в один сопоставление максимальной мощности в графике.^[1] Альтернативный термин допустимый край.^[2]^[3]

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

Мотивация

Рассмотрим сватовство агентство с пулом мужчин и женщин. Учитывая предпочтения кандидатов, агентство составляет двудольный граф где есть грань между мужчиной и женщиной, если они совместимы. Конечная цель агентства - создать как можно больше совместимых пар, т. Е. Найти сопоставление максимальной мощности в этом графике. Для достижения этой цели агентство сначала выбирает ребро в графе и предлагает мужчине и женщине на обоих концах ребра встретиться. Теперь агентство должно позаботиться о выборе только максимально подходящего края. Это связано с тем, что, если он выбирает край, не поддерживающий максимальное соответствие, он может застрять с ребром, которое не может быть завершено до соответствия максимальной мощности.^[1]

Определение

Позволять г = (V,E) - граф, где V вершины и E края. А соответствие в г это подмножество M из E, такая, что каждая вершина в V примыкает не более чем к одному ребру в M. А максимальное соответствие паросочетание максимальной мощности.

Край е в E называется максимально подходящий (или позволил), если существует максимальное соответствие M который содержит е.

Алгоритмы для общих графиков

В настоящее время самый известный детерминированный алгоритм для общих графов работает во времени. ${ displaystyle O (VE)}$ .^[2]

Существует рандомизированный алгоритм построения общих графиков по времени. ${ displaystyle { tilde {O}} (V ^ {2.376})}$ .^[4]

Алгоритмы для двудольных графов

В двудольных графах, если один сопоставление максимальной мощности известно, можно найти все максимально согласованные ребра за линейное время - ${ Displaystyle О (В + Е)}$ .^[1]

Если максимальное соответствие неизвестно, его можно найти с помощью существующих алгоритмов. В этом случае итоговое общее время выполнения будет ${ Displaystyle O (V ^ {1/2} E)}$ для общих двудольных графов и ${ Displaystyle О ((V / журнал V) ^ {1/2} E)}$ для плотных двудольных графов с ${ Displaystyle E = Theta (V ^ {2})}$ .

Двудольные графы с идеальным соответствием

Алгоритм поиска максимально совпадающих ребер проще, если граф допускает идеальное соответствие.^[1]^{:подраздел.2.1}

Пусть двудольный граф ${ Displaystyle G = (X + Y, E)}$ , где ${ Displaystyle X = (x_ {1}, ldots, x_ {n})}$ и ${ Displaystyle Y = (y_ {1}, ldots, y_ {n})}$ . Пусть будет идеальное совпадение ${ Displaystyle M = {(x_ {1}, y_ {1}), ldots, (x_ {n}, y_ {n}) }}$ .

Теорема: край е максимально совместима, если и только если е входит в некоторые М-переменный цикл - цикл, который чередуется между ребрами в M и края не в M. Доказательство:

Если е находится в чередующемся цикле, то либо е в M, или - инвертируя цикл - мы получаем новое идеальное соответствие, которое содержит е. Следовательно, е максимально совместимы.
Наоборот, если е максимально совпадает, то он находится в некотором идеальном соответствии N. Взяв симметричную разность M и N, мы можем построить переменный цикл, содержащий е.

Теперь рассмотрим ориентированный граф ${ Displaystyle H = (Z, E)}$ , где ${ Displaystyle Z = (z_ {1}, ldots, z_ {n})}$ и есть край от ${ displaystyle z_ {i}}$ к ${ displaystyle z_ {j}}$ в ЧАС если только ${ displaystyle i neq j}$ и есть грань между ${ displaystyle x_ {i}}$ и ${ displaystyle y_ {j}}$ в г (заметим, что по предположению таких ребер нет в M). Каждый M-переменный цикл в г соответствует направленный цикл в ЧАС. Направленное ребро принадлежит ориентированному циклу тогда и только тогда, когда оба его конца принадлежат одному и тому же компонент сильной связности. Существуют алгоритмы для нахождения всех сильносвязных компонент за линейное время.Поэтому множество всех максимально совпадающих ребер можно найти следующим образом:

Учитывая неориентированный двудольный граф ${ Displaystyle G = (X + Y, E)}$ и идеальное соответствие Mотметьте каждый край ${ Displaystyle (х_ {я}, у_ {я})}$ в M как максимально подходящие.
Построить ориентированный граф ${ Displaystyle H = (Z, E)}$ как указано выше.
Найдите все сильно связанные компоненты в ЧАС.
Для каждого я, j такой, что ${ displaystyle (z_ {i}, z_ {j})}$ находятся в одном компоненте, отметьте край ${ displaystyle (x_ {i}, y_ {j})}$ как максимально подходящие.
Отметьте все оставшиеся ребра как несовместимые.

Двудольные графы без идеального соответствия

Пусть двудольный граф ${ Displaystyle G = (X + Y, E)}$ , где ${ Displaystyle X = (x_ {1}, ldots, x_ {n})}$ и ${ Displaystyle Y = (y_ {1}, ldots, y_ {n '})}$ и ${ Displaystyle п Leq п '}$ . Пусть данное максимальное совпадение будет ${ Displaystyle M = {(x_ {1}, y_ {1}), ldots, (x_ {t}, y_ {t}) }}$ , где ${ Displaystyle т Leq п Leq п '}$ . Края в E можно разделить на два класса:

Ребра с обоими конечными точками, насыщенными M. Мы называем такие ребра M-верх.
Ребра с ровно одной конечной точкой насыщены M. Мы называем такие ребра М-нижний.
Обратите внимание, что нет ребер с обеими конечными точками, ненасыщенными на M, поскольку это противоречило бы максимальности M.

Теорема: Все M- нижние края максимально совместимы.^[1]^{:подраздел.2.2} Доказательство: предположим е = (Икс_я,у_j) где Икс_я насыщен и у_j не является. Затем, удалив (Икс_я,у_я) из M и добавив (Икс_я,у_j) дает новое соответствие максимальной мощности.

Следовательно, остается найти максимально совпадающие ребра среди M- верхние.

Позволять ЧАС быть подграфом г вызванный M-насыщенные узлы. Обратите внимание, что M идеальное сочетание в ЧАС. Следовательно, используя алгоритм предыдущего пункта, можно найти все ребра, которые максимально совпадают в ЧАС. Тасса^[1] объясняет, как найти оставшиеся максимально совместимые ребра, а также как динамически обновлять набор максимально совпадающих ребер при изменении графа.

использованная литература

^ ^а ^б ^c ^d ^е ^ж Тасса, Тамир (16 марта 2012 г.). «Нахождение всех максимально совместимых ребер в двудольном графе». Теоретическая информатика. 423: 50–58. Дои:10.1016 / j.tcs.2011.12.071. ISSN 0304-3975.
^ ^а ^б Де Карвалью, Марсело Х .; Чериян, Джозеф (01.10.2005). "An ${ displaystyle O (VE)}$ алгоритм разложения на слух покрытых совпадениями графов ». ACM-транзакции на алгоритмах. 1 (2): 324–337. Дои:10.1145/1103963.1103969. ISSN 1549-6325.
^ Ловас, Ласло; Пламмер, Майкл (2009-08-18). Теория соответствия. Провиденс, Род-Айленд: Американское математическое общество. Дои:10,1090 / чел / 367. ISBN 9780821847596.
^ Рабин, Майкл O .; Вазирани, Виджай В. (1989). «Максимальное совпадение в общих графиках посредством рандомизации» (PDF). Журнал алгоритмов. 10 (4): 557–567. Дои:10.1016/0196-6774(89)90005-9..

[:0-1] а ^б ^c ^d ^е ^ж Тасса, Тамир (16 марта 2012 г.). «Нахождение всех максимально совместимых ребер в двудольном графе». Теоретическая информатика. 423: 50–58. Дои:10.1016 / j.tcs.2011.12.071. ISSN 0304-3975.

[DCC-2] а ^б Де Карвалью, Марсело Х .; Чериян, Джозеф (01.10.2005). "An ${ displaystyle O (VE)}$ алгоритм разложения на слух покрытых совпадениями графов ». ACM-транзакции на алгоритмах. 1 (2): 324–337. Дои:10.1145/1103963.1103969. ISSN 1549-6325.

[3] Ловас, Ласло; Пламмер, Майкл (2009-08-18). Теория соответствия. Провиденс, Род-Айленд: Американское математическое общество. Дои:10,1090 / чел / 367. ISBN 9780821847596.

[:2-4] Рабин, Майкл O .; Вазирани, Виджай В. (1989). «Максимальное совпадение в общих графиках посредством рандомизации» (PDF). Журнал алгоритмов. 10 (4): 557–567. Дои:10.1016/0196-6774(89)90005-9..

[1]

[2]

[3]

[4]