Как сгенерировать n ребер каждый между m узлами

Question

У меня проблемы с концептуализацией моей проблемы. Но по сути, если у меня есть m узлов, и я хочу создать не более n соединений для каждого узла. Я также хочу убедиться, что всегда существует путь от каждого узла к любому другому узлу. Мне нет дела до циклов.

У меня нет правильного словарного запаса, чтобы найти эту проблему уже существующей, хотя я уверен, что она должна где-то существовать.

Кто-нибудь знает место, где объясняется эта проблема, или знает ответ самостоятельно?

Answer 1

Самый простой способ - построить связующее дерево, чтобы убедиться, что все узлы соединены, затем добавить ребра, которые не нарушают максимальное число ребер на узел, пока у вас не будет целевого числа из них. В псевдокоде:

// nodes[] is a list of all m nodes in our graph
connected_nodes = nodes[0];
// add nodes one by one until all are in the spanning tree
for next_node = 1 to (m-1)
   repeat
      select node connected_nodes[k]   // randomly, nearest, smallest degree, whatever
   until degree(k) < n   // make sure node to connect to does not violate max degree
   add edge between nodes[next_node] and new node connected_nodes[k]
   add nodes[next_node] to connected_nodes[]
end for

// the graph is now connected, add the desired number of edges
for e = m+1 to desired_edge_count
   select 2 nodes i,j from connected_nodes, each with degree < n
   add edge between nodes i and j
end for