An algorithm for generating an undirected graph indicating the path to all nodes with the maximum degree?

Question

I am trying to create an undirected graph in which each node has the maximum degree associated with it. That is, if a node has a maximum degree of 2, it can connect to no more than two nodes (a connected node is allowed, but not 0). My problem is that I am trying to create a graph in which it can be obtained from one node to another. Currently, I can nodes "randomly" connect to each other, but the problem is that it can create separate graphs, i.e. If you have 10 nodes, then sometimes two charts of 5 nodes appear by chance. If anyone knows about an effective solution, I would love to hear it!

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

While I am trying to avoid this:

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

Answer 1

This problem is a fairly well-known problem of graph theory, solvable in polynomial time, the name of which I forget (which, probably, "I find a graph taking into account its sequence of degrees"). In any case, Kiraly’s decision is a great way to do this, explained much better here than me. This algorithm solves for exact graphs that satisfy a given sequence of degrees, but they are easy to modify for weaker constraints.

Answer 2

The obvious solution would be to build it like an N-shaped tree - if the maximum degree is two, you get a binary tree.

To make it non-directional, you will have pointers not only to the "child" nodes, but also a back pointer to the "parent" node. At least it is presumably that it does not take into account the degree of the node (if so, your degree ends twice as a doubly connected linear list instead of a tree).

Edit: after clarification, it seems like the latter is true. Although they are different (with links going in different directions), your first picture showing the desired result is a topologically simple linear linked list. As noted above, since you need an undirected graph, it ends up as a doubly linked list.

Answer 3

It looks like you already know what the graph should look like, so I believe that if you can use the depth search approach. Although the search during the first breath can be used to avoid recursion.

For example, if you have nodes 1-5 and k = 2, you can plot, starting with node 1, and then just randomly select an invisible node. For instance:

1 [Start at 1] 1-2 [expand 2, add edge(1,2) to graph] 1-2-3 [expand 3, add edge(2,3) to graph] 1-2-3-4 [expand 4, add edge(3,4) to graph] 1-2-3-4-5 [expand 5, add edge(4,5) to graph] 1-2-3-4-5-1 [expand 1, add edge(5,1) to graph] (this step may or may not be done) 

If the edge is never used twice, then the paths p will lead to the degree of p * 2 as a whole, and the degree of the start and end nodes depends on whether the routes are really tours. To avoid duplication of work, it is probably easier to simply outline the vertices as integers from 1 to N, and then create edges so that each vertex v connects to the vertex with the number (v + j) mod (N + 1), where j and (N + 1) co-prime <N-1. The last bit makes things a bit problematic, as the number of companions from 1 to N can be limited if N is not prime. This means that for certain values, solutions do not exist, at least in the form of a new Hamiltonian path / tour. However, if you ignore the cooperative aspect and just make j integers from 1 to p, go through each vertex and create edges (instead of using the path approach), you can make all vertices of degree k, where k is an even number> = 2. This is achieved in O (N * k), although it can be dropped to O (N ^ 2) if the co-prime method is used.

Thus, the path for k = 4 will look like this if it starts with 1, with j = 2:

 1 [Start at 1] 1-3 [expand 3, add edge(1,3) to graph] 1-3-5 [expand 5, add edge(3,5) to graph] 1-3-5-2 [expand 2, add edge(5,2) to graph] 1-3-5-2-4 [expand 4, add edge(2,4) to graph] 1-3-5-2-4-1 [expand 1, add edge(4,1) to graph] (this step may or may not be done) 

Since | V | = 5 and k = 4, the resulting edges form a complete graph, as expected. It also works, since 2 and 5 are joint.

Obtaining an odd degree is a little harder. First we get the degree k-1, then the edges are added so that the odd degree is obtained as a whole. It seems pretty easy to approach (with one or two exceptions) all odd-edge edges, but it seems impossible or at least very complicated with an odd number of vertices and requires careful selection of edges with an even number of vertices, the section of which is not easy to put into the algorithm . However, it can be approximated by simply selecting two unused vertices and creating edges between them, so that the vertices are not used twice, and the edges are not used twice.