Равномерное распределение ребер в двудольном графе - PullRequest
Новая
       41

Равномерное распределение ребер в двудольном графе

1 голос
/ 16 марта 2019

Мне дан двудольный и ориентированный граф, изначально без ребер.Один набор узлов называется субъектами, другой набор называется объектами.Края могут быть построены только от субъекта к объекту.Количество предметов (numSubj) и предметов (numObj) приведены соответственно.Кроме того, указано количество доступных ребер (numEdges).

Цель состоит в том, чтобы равномерно распределить ребра от объектов к объектам.Это означает, что все объекты должны иметь одинаковое количество исходящих ребер, аналогично все объекты должны иметь одинаковое количество входящих ребер.Каждый предмет и объект должны иметь хотя бы один связанный край.

Пожалуйста, предложите решение (например, в псевдокоде)

1 Ответ

0 голосов
/ 16 марта 2019

Прежде всего давайте индексировать все элементы в каждом наборе узлов от 1 до numSubj и от 1 до numObj.Давайте также предположим, что numSubj < numObj (если это не так, то просто переверните наборы, решите и переверните их снова).

Теперь вычислите общее число ребер, которое является lcm этих чисел, после того, какчем вы можете заключить количество исходящих ребер, разделив результат на numObj (A) и найдя входящие, разделив на numSubj (B).

После этого расчета для каждого субъекта создайтеребро к вычисленному количеству объекта, где число входящих ребер, 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
...