Нахождение минимального разреза неориентированного графа

25

Вот вопрос из прошлого экзамена, который я пытаюсь решить:

Для неориентированного графа с положительными весами я пытаюсь найти минимальный разрез. Я не знаю других способов сделать это, кроме использования теоремы о максимальном потоке. Но график ненаправленный, так как мне его направить? Я думал о направлении ребер на обоих концах, но тогда какая вершина будет источником, а какая вершина будет стоком? Или есть другой способ найти минимальный разрез? $G$ $w(e) \geq 0$

algorithms graph-theory Юзеф
источник

1

Если на исходном графике нет источника и цели, я думаю, вам придется попробовать несколько вариантов. (Для любых заданных

и

минимальный разрез не может разделять два.)

s

$s$

t

$t$

Рафаэль

Вы пытаетесь найти минимальное сечение для заданных узлов источника и стока или минимальное сечение графика?

Питер

@Peter: минимальное сокращение графика.

Юзеф

13

Существует множество алгоритмов для нахождения минимального разреза неориентированного графа. Алгоритм Каргера - это простой, но эффективный рандомизированный алгоритм.

Короче говоря, алгоритм работает, равномерно выбирая ребра случайным образом и сжимая их без удаленных петель. Процесс останавливается, когда остаются два узла, и эти два узла представляют разрез. Чтобы увеличить вероятность успеха, рандомизированный алгоритм запускается несколько раз. Выполняя пробежки, можно отследить самый маленький из найденных кроев.

Смотрите запись в Википедии для более подробной информации. Для лучшего ознакомления, ознакомьтесь с первой главой вероятности и вычислений: рандомизированные алгоритмы и вероятностный анализ Майкла Митценмахера и Эли Апфала.

Юхо
источник

Это алгоритм приближения?

Стрин

@Strin Это рандомизированный алгоритм, который находит минимальное сокращение с высокой вероятностью.

Юхо

1

Я не думаю, что Karger's подходит для нахождения минимального веса. Вывод вероятности того, что он найдет минимальное сокращение, зависит от того, найдет ли он минимальное сокращение; Karger's вряд ли найдет минимальный крой со многими легкими краями.

Сумуду Фернандо

8

$(u,v, weight)$ $(u,v, weight)$ $(v,u,weight)$

... но тогда какая вершина будет источником, а какая вершина будет стоком?

Не имеет значения

Пратик Деогхаре
источник

1

Почему это не имеет значения?

Кодирование Wombat

1

Алгоритм Форда-Фулкерсона должен работать на вас. Вы можете создать две поддельные вершины, а именно. источник и раковина.

Также взгляните на алгоритм Эдмондса-Карпа . Есть два варианта этого:

Одна версия выбирает кратчайший путь
Другие выбирают путь с максимальной вместимостью

, в отличие от Форд-Фулкерсон, который выбирает произвольный путь.

Это хороший ресурс.

ajmartin
источник

Добро пожаловать в cs.stackexchange! Это могло бы помочь ОП, если бы вы могли более подробно объяснить, как фиктивные вершины связаны с существующим графом. И какими будут веса ребер новых ребер.

Paresh

Нахождение минимального разреза неориентированного графа

Ответы: