Gruppo di grafico a caso in base al numero di connessioni su ciascun nodo

Question

Sto cercando di generare un grafico basato su alcuni dati che ho.

Questo grafico dovrebbe avere nodi N in cui il numero di bordi ciascun nodo è uguale a un numero casuale P(k), in cui K è il "indice" del nodo (per lo più arbitrario).

La mia domanda è, c'è un modo reale per farlo?Sto pensando di aver bisogno di più dati che determinano la densità o un altro grado di collegamenti fuori (n1-> n2-> n3), ma non sono del tutto sicuro.

Answer 1

Vuoi essenzialmente generare un grafico con una certa sequenza di laurea (che vuoi essere casuale, ma questo non è rilevante); Questo è chiamato Problema di realizzazione del grafico che è risolto E.G. da algoritmo di Havel-hakimi nel senso che l'algoritmo tornerà Un grafico (semplice) con la sequenza di laurea desiderata se ciò è possibile (tali sequenze sono chiamate grafica ). Si noti che non tutte le sequenze finite su $ \ MathBB N $ sono grafica come E.G. Qualsiasi sequenza i cui membri sommano a un numero dispari non possono essere grafica da handshake lemma (che afferma questo La somma di tutti i gradi in un grafico è uguale a 2 volte il numero di bordi in un grafico e quindi anche). Inoltre, le soluzioni in generale non saranno univoche: la sequenza di laurea $ (2, 2, 2, 2, 2, 2) $ Ad esempio può essere realizzato dal Grafico del ciclo $ c_6 $ di taglia $ 6 $ o il disgiunto Union $ C_3 \ mathop {\ dot \ cup} c_3 $ di due grafici cicli $ c_3 $ di taglia $ 3 $ ciascuno.

Molte librerie grafiche per le lingue di programmazione hanno implementazioni di algoritmi per questo problema, ad esempio la libreria Python networkx .