modello di grafo casuale

Question

Quando si dice che nel grafo casuale aggiungiamo un bordo con una certa probabilità fisso, che cosa in realtà significa?

Per esempio, se la probabilità è 0,5, questo significa che possiamo solo aggiungere due bordi in un grafico perché 0,5 + 0,5 = 1.

Answer 1

Supponiamo che si desidera calcolare il grafo casuale $ G (n, p) $ che è il grafico con $ n $ vertici in cui si aggiunge ogni bordo con probabilità p $. $

Si supponga di avere una moneta che dà code con probabilità $ P $ e testa con probabilità $ 1 p. $

Quindi quello che si fa a prendere $ \ {1, ..., n \} $ di essere l'insieme dei vertici del grafico e per ogni coppia $ (i, j) \ in {\ {1, \ ldots, n \} \ scegliere 2} $ si ribalta la vostra moneta. Se si tratta croce si aggiunge il bordo $ (i, j) $ per il grafico altrimenti non.

Answer 2

Nel caso $ G (n, p) $ del modello, ciascuno dei $ \ binom {n} {2} $ bordi viene aggiunta al grafico con probabilità p $ $ in modo indipendente . Ciò significa che, se si considera qualsiasi due bordi, poi entrambi sono nel grafico con probabilità p $ ^ 2 $, non $ 2p $.

Answer 3

In aggiunta a ciò che viene detto, che è corretto, è possibile costruire un grafo casuale $ G (n, p) $ a $ 0 \ leq p \ leq 1 $ nel seguente modo:

Si supponga di avere una serie di vertici $ V $ e bordi vuoti $ E $. Per ogni $ $ v in $ V $: Per ogni $ u $ a $ V $ (dove $ u> v $ rispetto a qualche ordine totale tra i nodi di $ V $): generare un numero casuale uniforme $ r $ dove $ r \ in [0,1] $. Se ($ r \ leq p $) quindi includono il bordo $ (v, u) $ e $ (u, v) $ a $ E $.

Questo genera un grafo casuale $ G = (V, E) $ denotata $ G (n, p) $ dove $ | V | = N $. Questo tuttavia è un grafo orientato. Se si vuole rendere un grafo orientato, che, come questo caso non segue la definizione, quindi aggiungere solo il grafico $ (v, u) $.