在最近的一次计算中,我被要求设计一种算法,即for a network having V vertices and E edges, if by adding an edge (it's capacity should be 1) results in increase the maximum flow.,我们必须设计这样的算法来找到这样的边。
算法应该比O(|E|* h(|V||E|))更快,其中h(|V||E|)是计算最大流所用的时间。
提前谢谢。如果不清楚,请告诉我。
我想使用最大流算法(Edmond Karp / Ford-Fulkerson算法)找出无向图的边连通性(即,要移除以断开图的最小边数),
我知道我可以通过找到图的每两个节点之间的最小最大流来完成这项任务,但这将导致O(|V| ^ 2)个流网络,
int Edge-Connectivity(Graph G){
int min = infinite;
for (Vertex u: G.V){
for (Vertex v: G.V){
if (u != v){
//create directed graph Guv (
我正在使用JGraphT,我使用EdmondsKarpMFImpl。
问题是:如何定义所有的边缘--什么是“参与”?
我试着使用getCutEdges方法,但它只返回1边。
我有以下图表:
(所有边都有一个权重值(1)和一个剩余容量值(10))
public SimpleDirectedWeightedGraph generateAbilene(){
Supplier<Integer> vSupplier3 = new Supplier<Integer>() {
private int id = 1;
给定一个加权有向图,我们想要找到全局最小割集--也就是说,一组边,如果去掉这些边,就会将图分成两半,并且与任何其他的割集相比,它们的总重量最小。
现在,尽管下面这些似乎有效,但我被告知推理是错误的。但坦率地说,我不知道他是怎么做到的,我也不确定他有多确定:
考虑由全局最小割集(即s-t- U,V,其中s in U, t in V)分隔的节点集。注意:我们不关心从V到U的边缘。
对于任何u in U, v in Vm,u-v-切不能小于s-t-cut,否则,s-t-削减将不是(全局的)最小。出于同样的原因,u中的两个顶点之间或V中的两个顶点之间的切线都不可能更小。
另一方面,u-v切割也不可能更
给定一个参数k,我试图从有向图中删除k个边,这样最大流就会尽可能地减少。这个图有一个源和一个接收器t,每个边的容量是一个。图可能包含循环,也可能不包含循环。
我建议的解决方案是首先对图执行拓扑排序,使用“宽恕”循环的算法--也许是通过忽略将我们带回源的边缘。然后(假设k >= 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) th
我想知道最大流量和最小切割之间著名的二元性是否真的容忍无限有价值的容量。这里有一个简单的例子,但似乎并非如此:
信源s、信宿t、其他五个节点a、b、c、d、e
S -> a:容量3
S -> b: 3
A -> c:\infty
A -> d:\infty
B -> d:\infty
B -> e:\infty
C -> t: 1
D -> t: 1
E -> t: 4
最大流量是5。然而,没有容量为5的割集。这是因为无限的容量迫使所有a,b,c,d,e属于同一集合/割集的一半(否则在割集中会有一个\infty权重)。
我需要用这样的方式划分一个图,即节点X和节点Y不再连通。另外,移除的边的权重之和必须是最低的。
例如:
3 1 2
X ----- Z ----- W ----- Y
应成为:
3 2
X ----- Z W ----- Y
我首先认为我可以用一个循环来计算X和Y之间的最短路径,并去掉最便宜的边,直到没有更多的路径为止。然而,经过思考,我意识到这种方法并非在所有情况下都有效。
维基百科的搜索给我带来了Kernighan-Lin和Fiduccia-Mattheyses算法,但它们似乎是为了解决其他分区问题。
有标准的