Min s-t cut in network

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

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

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

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

15
задан 11 November 2011 в 14:59
поделиться