3 максимальный поток доказать или опровергнуть небольшие вопросы

Question

Вопросы:

поскольку (а) кажется, что это не так, мы можем найти пример роста потока без насыщения е.

для (б) это кажется правдой, но я не уверен, как это доказать. Может быть, из-за минимального среза максимального расхода, он был на минимальном срезе, поэтому он должен был расти.

для (с) это кажется ложным. поток вырос, потому что он изменился, но, возможно, не вырос ровно на 5.

Answer 1

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

(2) ложно. Возьмем такой график:

s --20-- n --20-- t

куда s является источником и t раковина, есть два мин-сокращения ({(s, n)} а также {(n, t)}), но увеличивается либо (s, n) или же (n, t) не изменит максимальный поток.

(3) является ложным. Возьмем такой график:

s --20-- n --25-- t

Если я увеличу емкость e = (s, n) от 10, то новый максимальный поток 25, но я не увеличил значение e от 5,

Answer 2

Для (1):

Максимальный поток в сети увеличился с 20 до 30 за счет увеличения пропускной способности e и мы должны доказать это e должно быть был насыщен до увеличения.

Рассмотрим обратное, что e не был насыщен до увеличения. В этом случае тогда должно существовать ребро (или группа ребер) e' где весь поток через e также проходит через e' и что максимальный поток сети ограничен пропускной способностью через ребро (я) e' такой, что capacity(e') < capacity(e) (иначе e будет насыщенным).

Учитывая это, если мы увеличим capacity(e) тогда мы все еще в ситуации, когда capacity(e') < capacity(e) и максимальный поток сети не будет затронут увеличенной емкостью.

Это противоречие (так как увеличение емкости e увеличил максимальный расход); так e должен быть насыщенным (и вы можете принять его к сведению, что если e' существует, то не может быть насыщен для увеличения максимального потока).

Например:

    /-- 10 --\ 
source      node -- 30 -- sink
    \-- 10 --/

        e'           e

График выше демонстрирует противоречие, где максимальный поток ограничен емкостью двух ребер e' от источника к узлу и e (от узла к раковине) не насыщается и увеличивается e не будет увеличивать максимальный поток.

Тем не мение,

    /-- 15--\ 
source      node -- 20 -- sink
    \-- 15 --/

        e'           e

На этом графике e насыщен (и e' не насыщен ) and increasing the capacity of e` до 30 (или более) увеличит максимальный поток графика до 30.

Что касается прочего:

• увидеть ответ Холта