我有一个问题,其中我有一个带加权边的二部图。我想要做的是,每个顶点上的边的权重之和,每一个点的权重。
最终的目标是将每个顶点上的权重事件转换为%,并使用一个置信区间来执行某些操作。
我现在正在处理这个问题,通过建立一个邻接矩阵来表示二分图。我打算在图的一组节点上迭代,并用连接边的权重更新矩阵中的相关单元。
有没有更好的方法来解决这个问题?
注意:我并不是在寻找像匈牙利算法那样的1:1匹配算法。我没有必要找到一个匹配的,只是一个%的基础上的权利的边缘。
发布于 2019-01-25 10:25:22
考虑一个具有5个顶点和两个顶点集U= { v1,v2,v3}和V= { v4,v5}.Note的二分图,在任何二部图中,同一顶点集的元素之间没有边,例如v1和v2或v4和v5。

所以你可以构造一个邻接矩阵,用U中的顶点作为行,V中的顶点作为列:
v4 v5 |sum(w)
|
v1 0 7 | 7
|
v2 6 0 | 6
|
v3 10 2 | 12
__________________
sum(w) 16 9这样,行和将给出U中顶点上入射边的权重之和,而列和则在V中的顶点上。
希望这能帮上忙!
https://stackoverflow.com/questions/54360202
复制相似问题