algorithm - una - probabilidad de lanzar un dado 3 veces

Crear todos los gráficos fuertemente conectados con grados dados con igual probabilidad

Question

Estoy buscando una forma de muestrear uniformemente desde el espacio de todos los gráficos dirigidos fuertemente conectados (sin bucles propios) de n nodos y en grados k=(k_1,...,k_n), 1 <= k_i <= n-1 .

Entrada

• n , la cantidad de nodos
• k = (k_1,...,k_n) , donde k_i = número de bordes dirigidos que entran en el nodo i (en grado)

Salida

• un gráfico dirigido fuertemente conectado de n nodos (sin bucles k_1,...,k_n ) con los grados en grados k_1,...,k_n en los que cada posible gráfico de este tipo se devuelve con la misma probabilidad.

Me interesan particularmente los casos en que n es grande y k_i es pequeño, por lo que simplemente es k_i crear un gráfico y verificar la conectividad fuerte porque la probabilidad es esencialmente cero .

Revisé todo tipo de documentos y métodos, pero no pude encontrar nada que trate este problema.

Answer 1

Sigue creando una ruta aleatoria hasta que haya un bucle:

node1-> node2-> node3 ...-> nodek-> noder donde r <= k

Ahora, reemplace el ciclo noder-> noder + 1-> nodek con un blob y permítanos llamarlo blobr. Ahora continúe conectándola a los nodos restantes (de modo que los nodos no estén en este blob). Cada vez que tocas un ciclo, simplemente crea un blob más grande.

Esto finalmente creará un gráfico dirigido aleatorio mínimamente fuerte. Después, agregue bordes al azar para cumplir los criterios de entrada.

Esto definitivamente creará todas las combinaciones de sus requisitos. Creo que todas las combinaciones son igualmente probables, pero tengo que pensar más.

Algoritmo: este es un esquema aproximado. En realidad, no estoy reconfigurando la estructura del gráfico aquí y no abordando las condiciones del borde, pero eso debería ser bastante directo.

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)