modèle de graphe aléatoire

Question

Quand nous disons que dans le graphique aléatoire, nous ajoutons un bord avec une certaine probabilité fixe, qu'est-ce que nous signifie réellement?

Par exemple, si la probabilité est de 0,5, est-ce que cela veut dire que nous pouvons simplement ajouter deux bords dans un graphique, car 0,5 + 0,5 = 1.

Answer 1

Supposons que vous souhaitez calculer le graphe aléatoire $ G (n, p) $ qui est le graphique avec $ n sommets $ où chaque bord est ajouté avec une probabilité $ p. $

Supposons que vous ayez une pièce de monnaie qui donne des queues avec une probabilité $ p $ et têtes avec une probabilité $ 1 p. $

Alors ce que vous faites vous prendre $ \ {1, ..., n \} $ pour être l'ensemble des sommets de votre graphique et pour chaque paire $ (i, j) \ dans {\ {1, \ ldots, n \} \ choose 2} $ vous retournez votre pièce. Si elle vient queues que vous ajoutez le bord $ (i, j) $ à votre graphique sinon vous ne sont pas.

Answer 2

Dans le $ aléatoire G (n, p) $ modèle, chacun des $ \ binom {n} {2} $ bords est ajouté au graphe de $ probabilité $ p indépendamment . Cela signifie que si l'on considère les deux bords, puis les deux sont dans le graphique avec une probabilité $ p ^ 2 $, pas $ $ 2 p.

Answer 3

En plus de ce qui est dit, ce qui est correct, vous pouvez construire un graphe aléatoire $ G (n, p) $ 0 $ \ leq p \ leq 1 $ comme suit:

Supposons que vous avez un ensemble de sommets $ V $ et $ E bords vides $. Pour chaque $ v $ en $ V $: Pour chaque $ u $ à $ V $ (où $ u> v $ par rapport à un ordre total entre les noeuds de V $ $): générer un nombre aléatoire uniforme $ r $ où $ r \ dans [0,1] $. Si ($ r \ leq p $) comprennent alors le $ de bord (v, u) $ et (u, v) $ $ à $ E $.

Cela génère un graphe aléatoire $ G = (V, E) $ G $ dénotée (n, p) $ où $ | V | = N $. Ceci est cependant un graphe orienté. Si vous voulez faire un graphe orienté, qui, comme ce cas ne suit pas la définition, puis ajouter que le graphique $ (v, u) $.