1
$\begingroup$

Recall that a closed walk (in a undirected graph) is a cycle if its vertices are pairwise distinct.

Does there exist random constructions of bipartite graphs without cycles with high probability?

  • 0
    You might be looking for [LERW](http://en.wikipedia.org/wiki/Loop-erased_random_walk) and [UST](http://en.wikipedia.org/wiki/Loop-erased_random_walk#The_uniform_spanning_tree).2012-06-04

1 Answers 1

2

If a graph has no cycles then it is clearly bipartite. Moreover a graph without cycles is a forest. So what you really want is generate trees/forests?

If you're looking to generate random labeled forests/trees then this can be done efficiently using Prüfer sequences. Every such sequence chosen at random gives you a specific labeled tree.

Random non labeled forest are a bit harder to generate.