Étant donné un graphique simple G, quelle est la façon la plus rapide connue de goûter à l'un de ses arbres couvrant au hasard?

Question

Disons que j'ai un graphique simple G avec un jeu de bord E, un jeu de sommet V et au moins 1 cycle.

Nous pouvons déterminer le nombre d'arbres couvrant dans ce graphique en trouvant sa matrice laplacienne graphique, en retirant une ligne et une colonne, puis en prenant le déterminant de cette sous-matrice.

Appelons cela déterminant t (c'est-à-dire qu'il y a des arbres couvrant possibles au total).

Quel est l'algorithme connu le plus rapide tel que son entrée est g et sa sortie est l'un des arbres couvrant possibles de g (où chaque arbre couvrant a aussi près de $ frac {1} {t} $ de chance d'être sélectionné que possible) ?

Voici l'algorithme que j'utilise actuellement.

---

Définitions:

$ V_ {visité} $ - Vertices déjà traversées

$ E_ {visité} $ - bords déjà traversés

$ V_c $ - v v_visite

N ($ v_ {visité} $) - L'ensemble de tous les sommets V dans $ v_c $ tel qu'un bord existe entre V et un sommet dans $ v_ {visité} $

---

Algorithme:

• Exemple de $ v_0 $ de V au hasard
• Ajouter $ v_0 $ à $ v_ {visité} $
• Exemple $ v_1 $ de n ($ v_ {visité} $) au hasard
• ajouter ($ v_0 $, $ v_1 $) à $ e_ {visité} $
• Exemple $ v_2 $ de n ($ v_ {visité} $) au hasard
• Ajouter ($ v _ * $, $ v_2 $) à $ e_ {visité} $ (où $ v _ * $ est choisi au hasard parmi les voisins de $ v_2 $ dans $ v_ {visité} $)

...

• Exemple de $ v_ {| v | - 1} $ (le deuxième au dernier sommet en v) au hasard
• Add ($ v _ * $, $ v_ {| v | - 1} $) à $ e_ {visité} $ (où $ v _ * $ est choisi au hasard parmi $ v_ {| v | - 1} $ $ V_ {visité} $)
• Exemple $ v_ {| v |} $ (le dernier sommet en v)
• Add (v *, $ v_ {| v |} $) à $ e_ {visité} $ (où $ v _ * $ est choisi au hasard parmi $ v_ {| v |} $ les voisins dans $ v_ {visité} $ $ )

Maintenant $ v_ {visité} $ et $ e_ {visité} $ représente un arbre couvrant aléatoire de G.

---

Est-ce la façon la plus efficace d'obtenir un arbre couvrant aléatoire? Y a-t-il un moyen plus efficace? (Points bonus si c'est parallélisable.)