Циркуляция в сетевом потоке

Question

Я читаю книгу Алгоритмов, написанную Робертом Седвиком.

Примечание: «s» - источник, а «t» - резервуар.

Augument любой сетевой поток с краем от «т» к «S» с потоком и мощностью, равной стоимости сети, и знать, что приток равен к оттоку для любого набора узлов в augumented сети. Такой поток называется циркуляцией, и эта конструкция демонстрирует, что проблема максимального потока сводится к проблеме нахождения циркуляции, которая максимизирует поток вдоль заданного края.

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

Генерация разложения потока: любая циркуляция может быть представлена ​​в виде потока по множеству самых близких циклов, направленных по E.

Мои вопросы по выше пояснении

1. Запрос объяснить с примером того, что делает автор в виду и как мы можем уменьшить «MaxFlow задача сводится к задаче нахождения циркуляции , которая максимизирует поток вдоль данный край ".?

2. Можно ли пояснить простым примером следующий параграф.

«Учитывая набор циклов и значение потока для каждого цикла, легко вычислить соответствующую циркуляцию, следуя через каждый цикл и добавление указанного потока к каждому краю. Обратное свойство Более удивительно: мы можем найти набор циклов (со значением расхода для каждый), что эквивалентно любому типу ».

Спасибо!

Answer 1

1. Если у вас есть проблемы MaxFlow с источником s и мойкой т, вы можете преобразовать эту проблему в максимальные проблемы циркуляции, просто добавив край t-> s. Первоначальный максимальный поток от s до t теперь преобразуется в максимальную циркуляцию s ---> t-> s.

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

   3(3)  2(2) 
   a ----> b -----> c 
   ^  |1(1) | 
   |3(3) V  V 2(4) 
   d<------e<-------f 
       3(4)  2(3) 
   

Соответствующие циклы: АБЭРА со значением потока 1 и abcfed с значением расхода 2. Эти два цикла вместе определяют максимальную циркуляцию, как показано выше.