最佳地減少最大流量

給定一個參數k，我試圖從有向圖中刪除邊緣，使得最大流量儘可能地減少。該圖有一個源s和接收器t，並且每個邊的容量是1。該圖可能包含或不包含週期。最佳地減少最大流量

我建議的解決方案是首先在圖上執行拓撲排序，使用「寬恕」循環的算法 - 可能忽略導致我們回到源的邊緣。然後（假設ķ> = 1）：

i = 0 
for each vertex u order by topological(u) 
    for each edge (u, v) order by topological(v) descending 
     if topological(v) > topological(u) then 
      delete (u, v) 
      if ++i = k then return 
     else 
      // edge doesn't contribute to max flow, ignore

請問

這項工作，還是我完全偏離軌道嗎？

來源

2010-04-11 ArIck

「找到最小切割」可以通過可以找到「最大流量」的算法來實現，例如Ford-Fulkerson算法。但是你究竟想要做什麼？減少最大流量意味着什麼？ – 2010-04-11 19:45:03

@Christian：我們的想法是，我們已經使用諸如Ford-Fulkerson等算法找到了最大流量，但是現在我們想要戰略性地刪除k條邊，以便儘可能地減少它。 – ArIck 2010-04-11 20:48:14

嗯，我記得去年在我的計算機科學課程中回答了這個確切的問題，我只是不記得我回答哈哈：P IIRC最大流算法將圖分成2組A，B，使得沿着邊的流從A到B是有能力的，這意味着這些邊緣是流動的「堵塞點」（在軍事術語中）。如果你削減這些邊緣，你肯定會減少最多的總流量。 – ldog 2010-04-12 17:43:34

我認爲你完全偏離軌道。您的算法可能根本不會減少流量，但可以將最大流量減少至少k（或使其爲0）。

你知道max-flow min-cut定理嗎？

來源

2010-04-11 18:07:05

我知道這是因爲我記住了「st流的最大值等於必須刪除的最小容量，所以沒有流可以從s到t」，但是我不清楚這將會怎樣在這種情況下幫助我。我們是否想在圖表中找到s-t切口，並帶走穿過切口的邊緣？ – ArIck 2010-04-11 18:26:23

@Arlck：我建議你自己試着回答這個問題。 – 2010-04-11 19:32:39

最佳地減少最大流量

回答

相關問題