Algorithm to generate an undirected graph with path to all nodes with a maximum degree?
algorithm, graph, graph-algorithm
Solution
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.
Problem
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! EDIT: 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: Whereas this is what I'm trying to avoid: 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.