Я пытаюсь найти максимальный независимый набор бипаритового графа.
В некоторых заметках я обнаружил следующее: «13 мая 1998 г. - Вашингтонский университет - CSE 521 - Приложения сетевого потока» :
Проблема:
Для двудольного графа найдите как можно большее независимое множество , где и . Множество является независимым, если между элементами множества нет ребер
Решение:
Построить потоковый граф на вершинах . Для каждого ребра существует бесконечное ребро емкости от до . Для каждого существует ребро единичной емкости от до , а для каждого существует ребро единичной емкости от до .
Найти конечный разрез емкости , с и . Пусть и . Множество является независимым, поскольку не существует бесконечных ребер емкости, пересекающих разрез. Размер разреза составляет , Это делается для того, чтобы сделать независимый набор как можно большим, мы делаем разрез как можно меньшим.
Итак, давайте возьмем это как график:
A - B - C
|
D - E - F
Мы можем разбить это на двудольный граф следующим образом
По поиску методом грубой силы мы можем видеть, что единственный Максимальный Независимый Набор - это . Давайте попробуем разобраться с решением выше:
Таким образом, построенная матрица смежности потоковой сети будет:
Вот где я застрял, наименьшее конечное снижение производительности, которое я вижу, является тривиальным: с мощностью 3.
Использование этого разреза приводит к неверному решению:
В то время как мы ожидали ? Может кто-нибудь определить, где я ошибся в своих рассуждениях / работе?
источник
Ответы:
Дополнением максимального независимого множества является минимальное покрытие вершин.
Чтобы найти минимальное покрытие вершин в двудольном графе, см . Теорему Кенига .
источник
Данное решение явно неверно, как вы продемонстрировали на контрпримере. Отметим, что граф U + V является связным компонентом ребрами бесконечной емкости. Поэтому каждый действительный разрез должен содержать все буквы A, B, C, D, E, F на одной стороне.
Попытка отследить, откуда пришло решение: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf цитирует сетевые потоки Ахуджи, Магнанти и Орлина для решения некоторых проблем. На эту книгу не распространяются авторские права и ее можно загрузить с http://archive.org/details/networkflows00ahuj, но в ней, похоже, нет этой проблемы и ее решения (поиск для каждого случая "двудольного").
Обратите внимание, что пояснительный параграф решения не показывает, что наименьший разрез построенного им графика соответствует максимальному независимому набору. Это только показывает способ получить в самостоятельный набор.
И все же, вы можете увидеть, что пытается сделать алгоритм. Вот что соответствует фактическому максимальному независимому набору с точки зрения его s, t cut:
Подчеркнуто ребро с бесконечной емкостью, нарушающее алгоритм.
Я не уверен, как исправить алгоритм в соответствии с тем, что было задумано. Может быть, стоимость бесконечного ребра должна быть равна нулю, если он идет в обратном направлении (т. Е. Куда он идет от S к T, но пересекает от t-стороны к s-стороне)? Но все же легко найти минимальный срез / максимальный поток с этой нелинейностью? Кроме того, если подумать о том, как соединить решение @Jukka Suomela с алгоритмом из этого вопроса, возникает трудность, когда мы переходим от максимального соответствия к минимальному покрытию вершин: в то время как нахождение максимального соответствия можно сделать с помощью максимального потока -подобный алгоритм, как вы восстанавливаете минимальное покрытие вершин из него, используя подобный потоку алгоритм? Как описано здесьпосле того, как максимальное совпадение найдено, ребра между U и V становятся направленными, чтобы найти минимальное покрытие вершин. Итак, опять же, это не показывает, что для решения этой проблемы достаточно простого применения min-cut / max-flow.
источник
Данный алгоритм корректен. Построенная сеть потока должна быть направлена, и значениеS -T вырезать учитывает только ребра, выходящие из множества вершин S ,
источник
Срез должен быть на фактическом потоке, а не на производительности. Поскольку поток из s конечен, любой {S, T} разрез будет конечным. Остальное объяснено выше.
источник
Я думаю, что вам не нужно соединять ребра в обоих направлениях, даже если исходный график был ненаправленным. Поскольку для сети потоков вам нужен ориентированный граф, вы можете рассмотреть только ребра изU в В ,
Тогда в этом новом графикеграмм' , у вас будет мин-2, что дает вам ответ { A , C, D , F} ,
источник