算法生成一个无向图与路径的所有节点，最大程度？ [英] Algorithm to generate an undirected graph with path to all nodes with a maximum degree?

问题描述

我试图产生无向图中，每个节点具有与其相关联的最大程度。也就是说，如果一个节点具有2的最大程度，它可以连接到最多两个节点（连接在节点将被允许，但不为0）。我的问题是，我试图生成一个曲线图中，它可能获得从一个节点到另一个节点。目前，我可以有节点随机连接到一个其它的，但问题是，其可以创建分割图形，即，如果你有10个节点，那么有时无意中两个图的5个节点每形式。如果有人知道的一个有效的解决方案，我很乐意听到它！

I'm trying to generate an undirected graph in which each node has a maximum degree associated with it. That is, if a node has a maximum degree of 2, it can connect to at most two nodes (connected node would be allowed, but not 0). My problem is that I'm trying to generate a graph in which its possible to get from one node to the other. Currently, I can have nodes "randomly" connect to one other, but the problem is that its possible to create divided graphs, ie if you have 10 nodes, then sometimes inadvertently two graphs of 5 nodes each forms. If anyone knows of an efficient solution, I'd love to hear it!

编辑：假设我有十个节点的曲线图，我指定2.最大程度在这种情况下，这里的东西，希望：

Suppose that I have a graph with ten nodes, and I specify a maximum degree of 2. In this case, here is something that would be desirable:

而这正是我想避免：

两个图具有2每个节点的最大程度，但是在第二图像，这是不可能选择一个任意节点，并能够得到的任何其他任意节点

Both graphs have a maximum degree of 2 per node, but in the second image, it's not possible to select an arbitrary node and be able to get to any other arbitrary node.

推荐答案

这问题是pretty的图论众所周知的问题，易溶于多项式时间，其中，名字我忘了（这可能是找到图给予其度序列）。总之，基拉伊的解决方案是一个很好的办法做到这一点，解释了好多这里不是我。此算法解决了满足给定程度的序列的确切图形，但应该很容易修改为您的更宽松的限制。

This problem is a pretty well-known problem in graph theory, soluble in polynomial time, the name of which I forget (which is probably "find a graph given its degree sequence"). Anyhow, Király's solution is a nice way to do it, explained much better here than by me. This algorithm solves for the exact graphs that satisfy the given degree sequence, but it should be easy to modify for your more loose constraints.

这篇关于算法生成一个无向图与路径的所有节点，最大程度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！