¿Cómo puedo generar aleatoriamente los árboles?

Question

Quiero generar aleatoriamente los árboles, es decir grafo acíclico gráficos con una sola raíz, asegurándose de que todos los posibles árboles con un número fijo de nodos n son igualmente probables.

Answer 1

Knuth dice mirarlo como a la generación de todos los paréntesis anidados en lexicográfica del orden.

Clic aquí para ver los detalles

http://www-cs-faculty.stanford.edu/~uno/fasc4a.ps.

Answer 2

Para generar un árbol al azar puede utilizar el siguiente algoritmo, donde dst y src son dos pilas:

dst := random permutation of all nodes;
src := empty stack
src.push(dst.pop()); % picks the root
while (!dst.empty()) {
  a := random element from src;
  b := dst.pop();
  add the edge (a, b)
  src.push(b);
}

La prueba de la corrección (todos los árboles son posibles y equiprobables): Alexey S. Rodionov y Hyunseung Choo, En la Generación Aleatoria de las Estructuras de la Red: los Árboles, los CCI DE 2003, LNCS 2658, pp 879-887, 2003.