知识卡片

普通读书笔记卡 · 3646.e.2.a

随机收缩逐边缩到两个超点

理解等级:中级

随机收缩算法反复均匀随机选一条边,将其两端点合并,并累加至其他顶点的平行边、移除自环;

只剩两个超点时,两者之间的边数对应原图某个割。

这张卡片看不懂?

已有反馈 · 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.