Erstellen all stark zusammenhängende Graphen mit Eingangsgrad mit gleicher Wahrscheinlichkeit gegeben

Question

ich nach einem Weg suchen gleichmäßig aus dem Raum zu probieren alle stark verbunden gerichtet Graphen (ohne Selbstschleifen) von n Knoten und Ein- Grad k=(k_1,...,k_n), 1 <= k_i <= n-1.

Eingangs

• n, die Anzahl der Knoten
• k = (k_1,...,k_n), wo k_i = Anzahl der gerichteten Kanten, die Knoten i (in Grad) eingeben

Output

• ein stark verbundener gerichteter Graph von n Knoten (ohne Selbstschleifen) mit den angegebenen In-Grad k_1,...,k_n wo jeder mögliche solche Graph mit der gleichen Wahrscheinlichkeit zurückgegeben wird.

Ich interessiere mich besonders für Fälle, in denen n groß ist und k_i ist klein, so dass lediglich ein Diagramm und die Überprüfung für eine starke Verbundenheit zu schaffen nicht machbar ist, weil die Wahrscheinlichkeit Null im Wesentlichen ist.

Ich sah mir alle möglichen Papiere und Methoden an, konnte aber nichts finden, was mit diesem Problem zu tun hat.

Answer 1

Halten eines Zufallspfad zu schaffen, bis es eine Schleife ist:

node1-> node2-> node3 ...-> nodek-> Noder wobei r = k <

Nun ersetzen den Zyklus Noder -> noder + 1-> nodek mit einem Blob und lasst uns es blobr nennen. Verbinden Sie es nun mit den verbleibenden Knoten (so dass die Knoten nicht in diesem Blob sind). Jedes Mal, wenn Sie einen Zyklus treffen, erstellen Sie einfach einen größeren Blob.

Dies wird letztlich einen zufälligen minimal starken gerichteten Graphen erstellen. Fügen Sie anschließend zufällige Kanten hinzu, um die eingehenden Kriterien zu erfüllen.

Dies wird definitiv alle Kombinationen Ihrer Anforderungen erstellen. Ich denke alle Kombinationen sind gleich wahrscheinlich, aber ich muss mehr nachdenken.

Algorithmus: Dies ist ein grobes Schema. Ich überarbeite die Graphenstruktur hier nicht und gehe nicht auf Randbedingungen ein, aber das sollte ziemlich geradlinig sein.

function randomStrongGraph(list<set<node>> chain, set<node> allnodes) 
    Node newnode = random(allnodes - head(chain)) 
    alreadyEncountered = false 
    for (i=0,i<chain.length-1;i++) 
     if (newnode in chain(i)) 
      consolidate(chain, i) 
      alreadyEncountered = true 
      break 
    if !alreadyEncountered 
     chain.append(new set().add(newnode))  
    randomStrongGraph(chain, allnodes)