在二分图中均匀分布边缘

Question

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

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

请建议一个解决方案（例如伪代码）

Answer 1

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

现在计算这些数字的lcm的边的总数，之后你可以通过将结果除以numObj（A）来结束输出边的数量，并通过除以numSubj（B）找到ingoing。

在对每个主题进行此计算之后，为计算的主题数创建一个边，其中进入边的数量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