Максимально подходящая кромка

В теории графов максимально сопоставляемое ребро в графе — это ребро, которое включено по крайней мере в одно сопоставление максимальной мощности в графе. ^[1] Альтернативный термин — разрешенное ребро . ^{[2] [3]}

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

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

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

Ребро e в E называется максимально паросочетаемым (или разрешенным ), если существует максимальное паросочетание M , содержащее e .

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

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

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

Если максимальное паросочетание неизвестно, его можно найти с помощью существующих алгоритмов. В этом случае результирующее общее время выполнения составляет для общих двудольных графов и для плотных двудольных графов с .${\displaystyle O(V^{1/2}E)}$${\displaystyle O((V/\log 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})\}}$

Теорема: ребро e является максимально совместимым тогда и только тогда, когда e включено в некоторый M - альтернирующий цикл — цикл, который чередует ребра из M и ребра не из M. Доказательство :

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

Теперь рассмотрим ориентированный граф , где и существует ребро из в в тогда и только тогда , когда и существует ребро между и в в (обратите внимание, что по предположению такие ребра отсутствуют в M ). Каждый M -альтернирующий цикл в G соответствует направленному циклу в H . Направленное ребро принадлежит направленному циклу тогда и только тогда, когда обе его конечные точки принадлежат одной и той же сильно связанной компоненте . Существуют алгоритмы для нахождения всех сильно связанных компонент за линейное время. Следовательно, множество всех максимально сопоставляемых ребер можно найти следующим образом:${\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)}$${\displaystyle (x_{i},y_{i})}$
• Постройте ориентированный граф, как указано выше.${\displaystyle H=(Z,E)}$
• Найдите все сильно связные компоненты в H.
• Для каждого i , j, находящегося в одном компоненте, отметьте ребро как максимально сопоставимое.${\displaystyle (z_{i},z_{j})}$${\displaystyle (x_{i},y_{j})}$
• Пометить все оставшиеся ребра как не максимально соответствующие друг другу.

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

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

Теорема: Все нижние ребра максимально сопоставимы. ^{[1] : подпункт 2.2} Доказательство : предположим, что где насыщено, а не насыщено. Тогда удаление из и добавление дает новое сопоставление с максимальной мощностью.${\displaystyle М}$ ${\displaystyle e=(x_{i},y_{j})}$${\displaystyle x_{i}}$${\displaystyle y_{i}}$${\displaystyle e=(x_{i},y_{j})}$${\displaystyle М}$${\displaystyle e=(x_{i},y_{j})}$

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

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