Двойное совпадение в двудольном графе - PullRequest
Новая
       6

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

0 голосов
/ 05 июля 2018

Я столкнулся со следующей проблемой изучения моего алгоритма, без опубликованного ответа:

  1. Задача максимального двойного соответствия - для двудольного графа G = (V = (LUR), E) описать алгоритм, который возвращает группу ребер M в E st для каждой вершины v в V, не более 2 ребра в M, которые включают v, максимального размера.

  2. Определение: «Сильное двойное соответствие» - это двойное соответствие st для каждой вершины v в V, есть по крайней мере одно ребро в M, которое включает v. Учитывая двудольный граф G = (V = (LUR), E) и сильное двойное соответствие M, опишите алгоритм, который возвращает сильное двойное соответствие M 'максимального размера. Докажите свой ответ.

так что мне уже удалось решить

1) использование приведения к максимальному потоку: добавление вершин s и t и ребер из s в L и ребер из R в t каждый с емкостью 2, и определение емкости каждого ребра между L и R с бесконечным вместимость. Нахождение максимального потока с использованием алгоритма Диника и возврат всех ребер с положительным потоком между L и R.

около 2) я думал о том, чтобы как-то манипулировать сетью, чтобы из каждой вершины был положительный поток, а затем каким-то образом использовать алгоритм для построения максимального решения. Какие-нибудь мысли? Ограничение времени выполнения O (V ^ 2E) (время выполнения Dinics)

1 Ответ

0 голосов
/ 06 июля 2018

Вот решение в O (n ^ 3), использующее минимальный поток затрат .

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

  1. Для каждой вершины u от L , добавить ребро единичной емкости от S до u ;
  2. Для каждого ребра uv , где u от L и v от R , добавьте край от u до v . Обратите внимание, что его емкость не имеет значения, если она хотя бы одна;
  3. Для каждой вершины v от R , добавьте ребро единичной емкости от u до R .

Теперь мы сохраним центральную часть и изменим левую и правую части.

  1. Для каждой вершины u от L , добавьте два ребра единичной емкости от S до u один из них стоил -1, а другой стоил 0;

То же самое для ребер v-> S .

Игнорирование стоимости, это та же сеть, которую вы построили сами. Максимальный поток здесь соответствует максимальному двойному совпадению.

Теперь давайте найдем минимальный поток затрат размером k . Это соответствует некоторому двойному сопоставлению, и из этого оно соответствует сопоставлению, которое касается максимально возможного числа вершин, потому что прикосновение к вершине (то есть проталкивание по крайней мере единичного потока через нее) уменьшает стоимость на 1. Более того, прикосновение к вершина во второй раз не уменьшает стоимость, потому что второе ребро стоило 0.

Как у нас есть решение: для каждого k = 1, ..., 2n итеративно найдите поток минимальных затрат и возьмите значение, соответствующее минимальной стоимости.

Использование алгоритма Джонсона (также называемого алгоритмом Дейкстры с потенциалами) дает O (n ^ 2) за итерацию, что в целом равно O (n ^ 3).

P.S. Время выполнения алгоритма Диника на единичных графах лучше, достигая O (E sqrt (V)) на двудольных графах.

...