Zufallsgrafikmodell

Question

Wenn wir sagen, dass wir in zufälligem Diagramm eine Kante mit einer bestimmten festen Wahrscheinlichkeit hinzufügen, was meinen wir tatsächlich?

Wenn beispielsweise die Wahrscheinlichkeit 0,5 beträgt, bedeutet dies, dass wir nur zwei Kanten in einem Diagramm hinzufügen können, da 0,5+0,5 = 1.

Answer 1

Angenommen, Sie möchten das zufällige Diagramm $ G (N, P) $ berechnen, das ist das Diagramm mit $ n $ verticals, wobei jede Kante mit Wahrscheinlichkeit $ p. $ Hinzugefügt wird

Angenommen, Sie haben eine Münze, die Schwänze mit Wahrscheinlichkeit $ P $ und Köpfen mit Wahrscheinlichkeit $ 1-p.

Dann, was Sie tun, nehmen Sie $ {1, ..., n } $ als die Scheitelpunkt -Set Ihres Diagramms und für jedes Paar $ (i, j) in { {1, ldots, n } Wählen Sie 2} $ Sie drehen Ihre Münze um. Wenn es Schwänze kommt, fügen Sie den Edge $ (i, j) $ zu Ihrem Diagramm hinzu, sonst nicht.

Answer 2

Im zufälligen Modell $ g (n, p) $ wird jeder der $ binom {n} {2} $ Kanten zum Diagramm mit Wahrscheinlichkeit $ P hinzugefügt unabhängig. Das heißt, wenn Sie zwei Kanten in Betracht ziehen, sind beide in der Grafik mit Wahrscheinlichkeit $ p^2 $, nicht $ 2p $.

Answer 3

Zusätzlich zu dem, was gesagt wird, was korrekt ist, können Sie ein zufälliges Diagramm $ G (n, p) $ für $ 0 Leq P Leq 1 $ erstellen wie folgt:

Angenommen, Sie haben eine Reihe von Scheitelpunkten $ v $ und leeren Kanten $ e $. Für jeden $ v $ in $ v $: für jeden $ u $ in $ v $ (wobei $ u> v $ in Bezug auf eine Gesamtbestellung unter den Knoten von $ v $): Generieren Sie eine einheitliche Zufallsnummer $ R $ wo $ r in [0,1] $. Wenn ($ r leq p $) dann den Edge $ (v, u) $ und $ (u, v) $ bis $ e $ enthalten.

Dies erzeugt eine zufällige Grafik $ g = (v, e) $ bezeichnet $ g (n, p) $ wobei $ | v | = n $. Dies ist jedoch ein gerichtetes Diagramm. Wenn Sie es zu einem gerichteten Diagramm machen möchten, der wie in diesem Fall nicht der Definition folgt, fügen Sie nur das Diagramm $ (v, u) $ hinzu.