Отказ от ответственности: это была проблема домашних заданий. Последний срок прошел, поэтому обсуждения могут продолжаться, не беспокоясь об этом.
Проблема, с которой я борюсь, заключается в том, чтобы определить, является ли конкретный минимум s-t разрезанным на графе G = (V, E) единственным. Это достаточно просто, чтобы найти минимальный разрез с использованием алгоритма максимального потока по в этом примере, но как бы вы показали ему min-cut?
Хорошо, так как вы не хотите сразу ответить на весь ответ, я дам вам несколько советов. Прочитайте столько, сколько вы считаете нужным для вас, и если вы сдаетесь - идите и прочитайте их все.
1
Разрез уникален, если нет другого минимального разреза.
2
Если вам удастся найти другой минимальный разрез, тогда первый минимальный разрез не уникален.
3
Ваша ссылка дала нам один min-cut, который является всеми достижимыми вершинами из s в остаточном графе. Можете ли вы придумать способ получения другого разреза, не обязательно то же самое?
4
Почему мы взяли эти вершины, достижимые от s в частности?
5:
Может быть, мы можем сделать что-то аналогичное от t?
6
Посмотрите на тот же остаточный график, начиная с t. Посмотрите на группу вершин, достижимую от t в обратном направлении стрелок (что означает все вершины, которые могут достигать t).
7
Эта группа также является min-cut (или фактически S \, эта группа, если быть точным).
8 (окончательный ответ):
Если этот разрез идентичен вашему первоначальному разрезу, тогда есть только один. В противном случае вы просто нашли 2 разреза, поэтому оригинал не может быть уникальным.
Структура:
Учитывая минимальный ST cut (U, V) с режущими кромками E ', сделаем одно простое наблюдение: если этот минимальный разрез не является уникальным, то существует некоторый другой минимальный разрез с множеством режущих кромок E '', что E ''!= E '.
Если это так, мы можем перебирать по каждому ребру в E ', добавлять к его емкости, пересчитывать максимальный поток и проверять, увеличилось ли оно.
В результате вышеизложенного существует ребро в E ', которое при увеличении максимального потока не увеличивается, если исходный разрез не является уникальным.
Я оставлю вас для заполнения деталей и докажу, что это многопользовательская задача.
Учитывая, что проблема с максимальным потоком/минимумом на самом деле является проблемой линейного программирования (первичная/двойственная соответственно), я рассматриваю любой метод проверки единственности решения ЛП и нахождения альтернативного оптимального решения, если его уникальность может быть использована в этом контексте. Я googled, чтобы найти эту статью: О уникальности решений линейных программ РЕДАКТИРОВАТЬ 1: Основываясь на предположении джуанга, для тех, кто не осознает, что теорема о максимальном потоке является частным случаем сильной теоремы двойственности в линейном программировании, вот ссылка, объясняющая этот нюанс: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Linear_program_formulation
Я немного запутался с ответом Эрана Циммермана (извините, что у меня недостаточно репутации, чтобы комментировать). Учитывая проблему максимального потока, может быть несколько решений, приводящих к различным остаточным графам. Даже если один из остаточных графов имеет только одно сокращение минимума, нет гарантии, что другие остаточные графы будут иметь точно такой же. Я желаю, чтобы кто-то мог бы объяснить это дальше.