首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >带加权边的二部图

问带加权边的二部图
EN

Stack Overflow用户
提问于 2019-01-25 06:43:52
回答 1查看 774关注 0票数 0

我有一个问题,其中我有一个带加权边的二部图。我想要做的是,每个顶点上的边的权重之和,每一个点的权重。

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

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

有没有更好的方法来解决这个问题?

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

EN

回答 1

Stack Overflow用户

发布于 2019-01-25 10:25:22

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

所以你可以构造一个邻接矩阵,用U中的顶点作为行,V中的顶点作为列:

代码语言:javascript
复制
        v4  v5   |sum(w)
                 |
    v1  0   7    | 7
                 | 
    v2  6   0    | 6 
                 |
    v3  10  2    | 12
__________________
sum(w)  16  9

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

希望这能帮上忙!

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/54360202

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档