Как может существовать ориентированный цикл в остаточном графе двусторонней потоковой сети с идеальным соответствием?

Я изучаю анализ алгоритмов. В настоящее время я читаю об алгоритмах Network Flow. Я рассматриваю применение Network Flow алгоритмов для поиска bipartite matchings минимальной стоимости.

  • Пусть G с соответствующим потоком сети G'
  • Пусть M будет perfect matching в G
  • Пусть G<sub>M</sub> будет residual graph, связанным с этим соответствием

Из Проектирования алгоритмов 7.13 на странице 406 Джона Клейнберга и Евы Тардос,

Theorem 7.62 заявляет:

(7.62) Пусть M - совершенное паросочетание. Если в G M есть цикл C с направленной отрицательной стоимостью, то M не является минимальной стоимостью

Однако эта теорема имеет смысл, я не понимаю, как bipartite flow network's residual graph из perfect matching может на самом деле содержать цикл. Единственный способ увидеть цикл - это задействовать sink или source.

Однако в perfect matching source не будет содержать ребер, выходящих из него, а sink не будет содержать ребер, входящих в него. Кроме того, цикл, происходящий во внутренних узлах, может противоречить определению Bipartite graph.

Может ли кто-нибудь привести пример такого цикла в остаточном графе?


graph algorithm computer-science network-flow bipartite
person Brian    schedule 08.04.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Конечно. Рассмотрим график, где a = стоимость и c = емкость:

  a=3,c=1
Ao----->oB
  \    ^
   \  /a=1,c=1
    \/
    /\
   /  \a=1,c=1
  /    v
Co----->oD
  a=3,c=1

Таким образом, очевидно, что существует 2 возможных максимальных потока. Один использует горизонтальные края, а другой - диагонали.

Для течения по горизонтали имеем остаточный граф:

  a=-3,c=1
Ao<-----oB
  \    ^
   \  /a=1,c=1
    \/
    /\
   /  \a=1,c=1
  /    v
Co<-----oD
 a=-3,c=1

Обратите внимание на цикл B-> A-> D-> C с мощностью 1 и стоимостью -3 + 1-3 + 1 = -4.

Интуитивно понятное объяснение этого цикла состоит в том, что при каждом увеличении потока на одну единицу, идущую по краям в цикле - или, наоборот, при каждом уменьшении потока, идущем по его краям в противоположном направлении - мы уменьшаем общую стоимость потока на 4, потому что мы будем заменять поток по более дешевым диагональным краям на поток по сравнительно дорогим горизонтальным краям.

В алгоритме увеличения пути для потока с минимальной стоимостью мы продвигаемся вперед и проталкиваем 1 единицу потока по этому циклу и в итоге получаем новый, более дешевый поток по диагоналям. Это даст новый остаточный граф:

  a=3,c=1
Ao----->oB
  ^    /
   \  /a=-1,c=1
    \/
    /\
   /  \a=-1,c=1
  v    \
Co----->oD
  a=3,c=1

Теперь цикл A-> B-> C-> D и имеет стоимость 3 - 1 + 3 - 1 = 4, поэтому максимальный поток по диагоналям равен минимальной стоимости и максимальному потоку.

person Gene    schedule 08.04.2014
comment
Очень хорошо объяснено вместе с хорошим графическим примером. Спасибо. - person Brian; 08.04.2014