Мин с-т режут в сети

Question

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

У меня есть сеть узлов с некоторыми пограничными мощностями.Это эквивалентно чему-то вроде проблемы сетевого потока в алгоритмах.Существует узел источника (который обнаруживает определенные события) и узел приемника (моя базовая станция).Теперь я хочу найти минимальный срез в сети, чтобы размер исходного набора был минимальным.Установленный здесь источник относится к набору узлов, разделенных минимальным вырезом, который содержит источник.

например, если st cut, C = {S,T}, то есть набор ребер, которые можно удалить, чтобы разделить сеть на два набора, S и T, а набор S содержитисточник и T содержит раковину.Отрез является минимальным, когда сумма мощностей кромок в надрезе минимальна среди всех возможных надрезов.Таких мини-разрезов может быть несколько.Мне нужно найти минимальный срез, который имеет наименьшее количество элементов в наборе S

Обратите внимание, что это не оригинальная проблема, но я попытался упростить ее, чтобы выразить ее в терминах алгоритмов,

Answer 1

Я полагаю, что вы можете решить эту проблему, найдя минимальное сечение на графике со слегка измененными ограничениями. Идея заключается в следующем: поскольку стоимость среза равна общей пропускной способности, пересекающей срез, мы могли бы попытаться изменить график, добавив дополнительное ребро от каждого узла в графе к 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 на графе 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 '

нК + | С | & GE; n (C '+ 1) + | S | = nC '+ n + | S |

Теперь обратите внимание, что 0 & le; | S |

nC + | S | & GE; nC '+ n + | S | > nC '+ | S' | + | S | > nC '+ | S' |

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

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

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

Answer 2

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

Подтверждение правильности: ясно, что S - минимальное сокращение (cut = setузлов в части, содержащей с).Предположим, что S * является сечением меньше, чем S (т. Е. | S * | <| S |).С помощью простого аргумента подсчета пусть u будет узлом в S - S *.Если мы добавим дугу положительной емкости от u к t, то вычисленный поток будет иметь путь расширения и больше не будет максимальным, но емкость среза S * не изменится, поскольку и u, и t принадлежат V - S *.Из слабой двойственности мы заключаем, что S * не является минимальным разрезом. </p>

Фактически, класс минимальных разрезов является дистрибутивной решеткой при пересечении и объединении, поэтому каждый экземпляр вашей задачи имеет уникальное решение.

Answer 3

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

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