如何在 m 个节点之间生成 n 个边

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

如何在 m 个节点之间生成 n 个边

How to generate n edges each between m nodes

graph

nodes

edges