Мин с-т разрез в сети

Я считаю, что вы можете решить эту проблему, найдя минимальный разрез в графе с немного измененными ограничениями. Идея заключается в следующем: поскольку стоимость разреза равна общей пропускной способности, пересекающей разрез, мы можем попробовать модифицировать граф, добавив дополнительное ребро из каждого узла графа в t с пропускной способностью, равной единице. Интуитивно это будет означать, что каждый узел в той же части разреза, что и s, внесет одну дополнительную стоимость в общую стоимость разреза, потому что ребро от этого узла до t будет пересекать ребро. Конечно, это определенно испортило бы реальное минимальное сокращение из-за дополнительной емкости. Чтобы это исправить, применим следующее преобразование — сначала умножим пропускные способности ребер на n, где n — количество узлов в графе. Затем добавьте по одному к каждому краю. Интуиция здесь заключается в том, что, умножив пропускную способность ребер на n, мы сделали так, что стоимость минимального разреза (без учета новых ребер от каждого узла до t) будет в n раз превышать первоначальную стоимость разреза. Когда мы затем добавим дополнительные ребра с одной пропускной способностью от каждого узла к t, максимальный возможный вклад этих ребер в стоимость разреза будет n - 1 (если все узлы в графе, кроме t, находятся на одной стороне). как с). Таким образом, стоимость старого минимального разреза была C, стоимость нового минимального разреза (S, V - S) равна nC + |S|, где |S| - количество узлов на той же стороне разреза, что и s.

Более формально конструкция выглядит следующим образом. Имея направленный граф с емкостью G и пару (источник, сток) (s, t), постройте граф G', выполнив следующие действия:

1. Для каждого ребра (u, v) в графе умножьте его пропускную способность на n.
2. Для каждого узла v в графе добавьте новое ребро (v, t) с пропускной способностью 1.
3. Вычислите разрез min s-t на графике.

Я утверждаю, что разрез min s-t в графе G' соответствует разрезу min s-t в графе G с наименьшим числом узлов на той же стороне разреза, что и s. Доказательство следующее. Пусть (S, V — S) — минимальное s-t сечение в G'. Во-первых, нам нужно показать, что (S, V — S) является минимальным s-t разрезом в G. Это доказательство от противного; предположим для противоречия, что существует s-t разрез (S', V — S'), стоимость которого ниже стоимости (S, V — S). Пусть стоимость (S', V - S') в G равна C', а стоимость (S, V - S) в G равна C. Теперь давайте рассмотрим стоимость этих двух разрезов в G'. По сужению стоимость C' будет равна nC' + |S'| (поскольку каждый узел на стороне S разреза вносит одну пропускную способность по разрезу), а стоимость C будет равна nC + |S|. Поскольку мы знаем, что C' ‹ C, мы должны иметь C' + 1 C. Таким образом,

nC + |S| ≥ n(C' + 1) + |S| = nC' + n + |S|

Теперь обратите внимание, что 0 |S| ‹ n и 0 |S'| ‹ n, потому что может быть не более n узлов на той же стороне разреза, что и s. Таким образом, означает, что

nC + |S| ≥ nC' + n + |S| > nC' + |S'| + |S| > nC' + |S'|

Но это означает, что стоимость (S, V - S) в G' больше стоимости (S', V - S') в G', что противоречит тому факту, что (S, V - S) является минимальным s-t разрезается на G'. Это позволяет заключить, что любой разрез min s-t в G' является также разрезом min s-t в G.

Теперь нам нужно показать, что разрез min s-t не только является разрезом min s-t в G', но и соответствует разрезу min s-t в G с наименьшим числом узлов на той же стороне разреза, что и s. . Опять же, это доказательство от противного; предположим, что (S, V — S) является минимальным s-t разрезом в G', но существует некоторый min s-t разрез в G с меньшим количеством узлов на s-стороне разреза. Назовите это лучшим разрезом (S', V - S'). Поскольку (S, V - S) является минимальным разрезом s-t в G', он также является разрезом min s-t в G, поэтому стоимость (S', V - S') и (S, V - S) в G равна некоторое число C. Тогда стоимость (S, V - S) и (S', V - S') в G' будет равна nC + |S| и nC + |S'| соответственно. Мы знаем, что nC + |S'| ‹ nC + |S|, так как мы выбрали (S', V - S') как разрез s-t min в G с наименьшим числом узлов на той же стороне, что и S. Но это означает, что (S', V - S') имеет меньшую стоимость, чем (S, V - S), что противоречит тому факту, что (S, V - S) является минимальным s-t разрезом в G'. Таким образом, наше предположение было неверным и (S, V — S) является минимальным s-t разрезом в G с наименьшим числом узлов на той же стороне, что и S. Это завершает доказательство корректности конструкции.

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

tl;dr Вычислите максимальный поток s-t и пусть S будет набором узлов, достижимых из s по дугам с положительной остаточной пропускной способностью.

Доказательство правильности: ясно, что S — это минимальный разрез s-t (разрез = множество узлов в части, содержащей s). Предположим, что S* — разрез s-t, меньший, чем S (т. е. |S*| ‹ |S|). По простому аргументу подсчета пусть u будет узлом в S — S*. Если мы добавим дугу с положительной пропускной способностью от u к t, то вычисленный поток будет иметь увеличивающий путь и больше не будет максимальным, но пропускная способность разреза S* останется неизменной, так как u и t оба принадлежат V — S*. Из слабой двойственности заключаем, что S* не является минимальным разрезом.

На самом деле класс разрезов s-t min представляет собой дистрибутивную решетку относительно пересечения и объединения, поэтому каждый экземпляр вашей задачи имеет единственное решение.

В вашем вопросе и комментарии, я думаю, вы говорите две разные вещи: во-первых, нахождение minmum s-t cut так, чтобы отделить источник узла и думать, и его вес минимален (вес будет рассчитываться путем удаления размеров ребер), и это можно сделать с помощью алгоритма Форда-Фулкерсона и вот пример реализации в java (также в Matlab есть функция graphmaxflow), также она доступна в библиотеке igraph.

Но, как ваш комментарий и первая часть вопроса, который вы задали для нахождения минимального разреза, так что количество узлов в части s сведено к минимуму, в этом случае вы должны удалить все ребра S, чтобы иметь группы размером 1,n-1, или вы должны перефразировать свой вопрос.