知识卡片
随机收缩逐边缩到两个超点
随机收缩算法反复均匀随机选一条边,将其两端点合并,并累加至其他顶点的平行边、移除自环;
只剩两个超点时,两者之间的边数对应原图某个割。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第24章 最大流 · 查看原书依据
The algorithm maintains a multigraph, so that upon contracting an edge (u, v), it creates a new vertex x, and for any other vertex y ∈ V, the number of edges between x and y is c(u, y) + c(v, y). The algorithm does not maintain self-loops, and so it sets c(x, x) to 0.
参考来源
- 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[60000,65000))。
- 结论依据:问题24-7先说明收缩时合并平行边并移除自环,再说明随机选边缩至两个超点与原图割的对应。
- 原始内容:The algorithm maintains a multigraph, so that upon contracting an edge ( u , v ), it creates a new vertex x , and for any other vertex y ∈ V , the number of edges between x and y is c ( u , y ) + c ( v , y ). The algorithm does not maintain self-loops, and so it sets c ( x , x ) to 0.
- 原文补充:Consider the algorithm that repeatedly chooses an edge at random and contracts it until the multigraph has exactly two vertices, say u and v . At that point, the multigraph corresponds to a cut in the original graph, with vertex u representing all the nodes in one side of the original graph, and v representing all the vertices on the other side.