Максимальное двустороннее соответствие в несвязном графе

Question

Как вы находите максимальное двойное соответствие, когда ваш график состоит из нескольких компонентов? Каждый компонент может быть окрашен двумя способами. Как вы решаете два набора X и Y для запуска процедуры максимального соответствия?

Answer 1

Если ваш график имеет несколько различных связанных компонентов, вы можете найти максимальное соответствие в графике, просто найдя максимальное соответствие в каждом из этих компонентов и возвратив их объединение.

Что касается того, как определить наборыX и Y, существует множество алгоритмов для определения того, является ли конкретный граф двудольным, и, если да, для назначения меток узлам для восстановления этих двух групп.Вы можете сделать это с помощью модифицированной DFS или BFS довольно легко.Следовательно, алгоритм для вашей проблемы может быть

1. Запустить DFS по всему графику, чтобы разбить его на связанные компоненты.
2. Для каждого из этих компонентов:
   1. Запустите DFS на этих компонентах, чтобы восстановить, какие узлы находятся в группах X и Y.
   2. Используйте алгоритм максимального двудольного сопоставления, чтобы найти максимальное совпадение в этом компоненте.
3. Объедините все результаты вместе, чтобы получить общий ответ.

Надеюсь, это поможет!

Answer 2

Не смотрите на совпадение с точки зрения ребер, посмотрите на как набор ребер . Эта точка зрения проясняет, что независимо от того, как вы присоединитесь к подрезультатам, с ним все равно будет нормально.

1. Разделите график на подключенные компоненты

2. Найдите максимальное соответствие для каждого компонента графа, используя ваш алгоритм выбора.

3. Объединение найденных совпадений является максимальным соответствием всего графа.

Answer 3

Я не знаю об отключенном графе, но если у вас есть полный граф, такой как у меня, это может быть вам интересно: http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html. Он использует модифицированный алгоритм Флойда-Варшалла для поиска максимального соответствия. Я не знаю о разнице между этим и венгерским алгоритмом.