最佳地减少最大流量

给定一个参数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

最佳地减少最大流量

回答

相关问题