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

Question

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

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

От Джона Клейнбергом и Ева Tardos' Algorithm Design 7,13 на странице 406,

Theorem 7.62 указывается:

(7.62) Пусть M - идеальное соответствие. Если есть отрицательная стоимость направленного цикл C в G _M, то М не минимальная стоимость

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

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

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

Answer 1

Несомненно. Рассмотрим график, где 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-> С емкостью 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 

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