To do this mathematically accurately, the question needs to be better specified.
What do we mean when we say "generate a random X"?
A more precise phrasing of the problem is "choose an X uniformly at random from the set of all Xs", with uniform being critical (i.e. each X is chosen with the same probability). For some applications, non-uniform sampling is also useful, but we would at least want to know what distribution we are sampling from.
Most suggestions you will find online about how to do this will neither sample uniformly, nor will they make it easy (or at all possible!) to figure out the actual distribution you are sampling from. This is also true for Nicola's suggestion above.
So let's make the question precise:
Do you want to sample uniformly from the set of all connected simple graphs on
$n$ vertices? Notice the two constraints: "connected" and "having
$n$ vertices". This task happens to be easy because most graphs on
$n$ vertices are connected. Thus we can use rejection sampling.
While[
Not@ConnectedGraphQ[
g = RandomGraph[BernoulliGraphDistribution[10, 1/2]]
]
]
g
BernoulliGraphDistribution[10, 1/2]
represents a uniform distribution over the set of all simple graphs on 10 vertices. We keep drawing graphs from this distribution until we find a connected one. With very high probability, the first one will already be connected.
Another version of the problem:
Sample uniformly from the set of connected simple graphs on
$n$ vertices with
$m$ edges. Now we have an extra constraint on the number of edges, and this makes the problem much harder. I am not aware of any simple and general solutions to this.
We can pick a graph at random with
$n$ vertices and
$m$ edges using RandomGraph[{n,m}]
, but some of these will not be connected. If m
is low, most of these will not be connected, thus rejection sampling is not feasible.
I asked a question about this on MathOverflow a while ago: https://mathoverflow.net/q/297317/8776
If you google for solutions, a typical suggestion is to first construct a random tree (there are several simple methods for uniform sampling of trees), which ensures connectedness. Then add more edges randomly. This method is incorrect. It does not sample uniformly, nor do the various blog posts suggestion this algorithm derive the actual distribution is samples from.
@Licheng Zhang, you mention using Sage for this problem. Can you specify which exact problem (see two possible versions above) and which Sage function you are using? I am interested in this topic too.