时间戳

首页 > 解决方案 > 二分图中边的均匀分布

algorithm - 二分图中边的均匀分布

问题描述

我得到一个二分有向图，最初没有边。一组节点称为主体，另一组称为对象。边只能从主体到客体构建。分别给出了主体（numSubj）和客体（ ）的数量。numObj此外，还给出了可用边的数量 ( numEdges)。

目标是将边缘从主体均匀分布到物体。这意味着所有主体都应该有相似数量的出边，类似地所有对象应该有相似数量的入边。每个主体和客体都必须至少有一个连接边。

请提出解决方案（例如在伪代码中）

标签： algorithmgraph-theorypseudocode

解决方案

首先，让我们索引每组节点中的所有项目，numSubj从 1 到 1 到numObj。让我们也假设numSubj < numObj（如果这不是真的而不是简单地翻转集合，解决并再次翻转它们）。

现在计算这些数字中的总边数，然后您可以通过将结果除以( )lcm得出出边数，并通过除以( ) 找到入边数。numObjAnumSubjB

在对每个主题进行此计算之后，为计算的主题数量创建一条边，其中进入边的数量 ,A小于计算的第二个数字 - B。

这个过程可以这样完成：
i连接到[i * B, i * B + 1, ... , i * (B + 1) - 1 ] mod numObj

2和5：_

LCM = 10  
Ingoing = 10 / 5 = 2  
Outgoing = 10 / 2 = 5   
1 -> 1, 2, 3, 4, 5   
2 -> 1, 2, 3, 4, 5

4和8：_

LCM = 8  
Ingoing = 8 / 8 = 1   
Outgoing = 8 / 4 = 2   
1 -> 1, 2   
2 -> 3, 4 
3 -> 5, 6  
4 -> 7, 8

4和6：_

LCM = 12 
Ingoing = 12 / 6 = 2   
Outgoing = 12 / 4 = 3   
1 -> 1, 2, 3   
2 -> 4, 5, 6 
3 -> 1, 2, 3  
4 -> 4, 5, 6

推荐阅读