How to Generate Random Connected Graphs
Разница между en1 и en2, 22 символ(ов) изменены
As the title says, I wanna generate random graphs that are connected. Now there are some details herr, obviously I want the graph to have $n$ nodes which is predetermined. Something else that arises in competitive programming is that the graph should have $m$ edges(also predetermined). Now how does one do that in an intelligent way.↵

Now I have done a little bit of googling, and 
uit seems there are no 'Ggood' way of getting a perfectly 'random' such graph i.e. pick one uniformly from all connected graphs with n nodes and m edges. But that's okay an, approximately random is also good.↵

One way I have considered is 
to make a spanning tree first, then add extra edges. But this has horrible bias for certain graphs. For example for $n$ node $n$ edge graph, a cycle graph $(1-2-3-...-n-1)$ is $\frac{n}{3}$ times more likely than path $(1-2-3-4-...-n)$ + edge $(1-3)$. So what process can be a good choice?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский upobir 2020-05-26 16:52:20 22
en1 Английский upobir 2020-05-26 16:23:39 936 Initial revision (published)