代码之家 › 专栏 › 技术社区 › random_coder_101

带权边的二部图

bipartite computer-science

0

random_coder_101 · 技术社区 · 6 年前

最终的目标是将每个顶点上的权重转换为%,并使用置信区间来执行某些操作。

我正在通过建立一个邻接矩阵来表示二部图来解决这个问题。我打算在图的一组节点上迭代,并用连接边的权重更新矩阵中的相关单元。

注意:我不是在寻找像匈牙利算法那样的1:1匹配算法。我不需要找到一个匹配,只是一个%的基础上的权重的边缘。

1 回复 | 直到 6 年前

1

Viseshini Reddy 6 年前

考虑一个有5个顶点和两个顶点集U={v1,v2,v3}和V={v4,v5}的二部图。注意,在任何二部图中,相同顶点集的元素之间都没有边,例如v1和v2或v4和v5。

        v4  v5   |sum(w)
                 |
    v1  0   7    | 7
                 | 
    v2  6   0    | 6 
                 |
    v3  10  2    | 12
__________________
sum(w)  16  9

这样,行和将给出U中顶点上的边的权重之和,列和将给出V中顶点上的边的权重之和。

希望有帮助!