Random Binary Graph Generation

Question

Is there a simple algorithm for creating a random undirected binary graph (given the number of vertices as input)? I understand how to determine if a given graph is binary, but I'm struggling to create it.

Answer 1

You can make a very simple probabilistic approach:

1. Create an empty graph with n nodes 2. For each pair of nodes: -Flip a fifty-fifty-coin to decide whether to put an edge in there or not 

You have a pair of O (n ^ 2) vertices, and this will also expect the running time of this algorithm, since the random graph generated by this procedure will most likely be tied to .

Therefore, in the end, to make sure that your schedule is really doubly connected, you simply run the usual procedure that you already know.

For a scenario (very unlikely) where the check returns “the graph is not doubly connected,” simply repeat the procedure.

A really intriguing question: "Why will I get the binary graph whp?" I omitted the formal proof, which is a bit tedious, and by the way you ask, I suppose you just want something to work, and you don't care why it works. If I'm wrong, and you really need proof, I suggest you either ask mathoverflow or leave me a comment - maybe I will try to make it formal if I take the time.

For now, just to make you feel why this will work, consider the following approach to how it can be proved:

• The number of graphs that are not doubly connected is equal to the number of graphs with at least one joint vertex.

• Therefore, calculate the probability that one vertex is an articulation point. The idea is that if v is the vertex of the articulation, then it divides the vertices of n into two disjoint sets of size k and nk , so there is no edge between these sets. Now, intuitively, it should be more or less clear that k*(nk) flipping coins, all of which should lead to "without edge", is not very likely (mostly (1/2)^(k*(nk)) ). We still need to multiply by n (since for each node), but it still will not become real, and, as you can see now, it is very unlikely that a graph with a sufficiently large number "n" is not doubly connected,

(What is still not enough to consider "for each possible partition", that is, for different variants of k , and then, perhaps, be more careful, since in reality it will be ((n-1)-k) and k , and not (nk) and k , because the vertex in question is not part of either of the two sets ... I just say that these things illustrate details that still have to worry about formal proof ...)

Answer 2

A simple way is to create a random maximum planar (three-connected) graph:

• Start with 3 vertices connected in a loop that forms two triangular faces (inside and outside the loop).
• To add each subsequent vertex, select a random face and draw it with a vertex and three edges.

You can stay here - since the count is trisconnected, it is also doubly connected.

However, if you want to remove edges and make sure you still have a binary graph, then remove only the edges where both falling vertices are of degree 3 or more, and check each edge before deleting using Hopcroft and Tarjan. Deep-first search algorithm to search for Biconnected Components to check for compatibility without this edge.

Note. This will always create a planar graph.