Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » E[X] eines zusammenhängenden Zufallsgraphen

E[X] eines zusammenhängenden Zufallsgraphen

Universität / Fachhochschule

Graphentheorie

Erwartungswert

Tags: Erwartungswert, Graphentheorie, Zufallsgraphen

klauszi aktiv_icon

23:59 Uhr, 31.07.2017

Hallo, Community!

Ich habe ein kleines Programm geschrieben, welches abhängig der Kanten- und Knotenanzahl einen Zufallsgraphen ausgibt. Die Implementation entspricht der Vorgehensweise von dem Erdős-Rényi-Graphen (wiki: Zufallsgraphen) , der von allen möglichen ungerichteten Kanten mit der Anzahl

\frac{n \cdot (n - 1)}{2}

(keine parallele Kanten!) von

n

Knoten genau

m

Kanten auswählt und zurückliefert.

Für die Laufzeitanalyse eines anderen Algorithmus wird von dem Zufallsgraphen erfordert, dass der Zufallsgraph zusammhängt, also von allen Knoten einen Pfad zu allen anderen Knoten existiert. Da meine Laufzeitanalyse nicht auf die Knotenanzahl gerichtet ist, sondern eher auf die Anzahl der Kanten, habe ich jeden resultierenden Zufallsgraphen die isolierten Knoten, also Knoten mit dem Grad 0, entfernen lassen. Der Zufallsgraph ohne isolierten Knoten wird genau dann zurückgegeben, wenn demnach alle nicht-isolierten Knoten zusammenhängen.

Meine Frage hierzu lautet, mit wie vielen Versuche von Zufallsgraphenerzeugungen ich rechnen muss, bis ein Zufallsgraphen erzeugt wird, der meinen Kriterien erfüllt? Wie gehe ich da am Besten vor? Literaturangaben zu dem Thema ist wünschenswert!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Mauthagoras aktiv_icon

08:17 Uhr, 01.08.2017

Hallo,

vielleicht kann ich zumindest ein bisschen helfen...

Ganz allgemein lässt sich Deine Situation als Wartezeitproblem mit geometrischer Verteilung beschreiben: Du sucht den Erwartungswert von

G

, wobei

G

der Zeitpunkt des ersten E-R-Graphen mit Parameter

(n, p)

ist, der
(i) genau

m

Kanten hat, oder
(ii) zusammenhängend ist.

Der erste Fall lässt sich relativ leicht lösen: Die Anzahl der Kanten des Graphen ist binomialverteilt mit Parameter

((\binom{n}{2}), p)

. Das heißt, die Wahrscheinlichkeit dafür, genau

m

Kanten zu haben, ist

q := (\binom{(\binom{n}{2})}{m}) p^{m} (1 - p)^{(\binom{n}{2}) - m}

G

ist nun geometrisch verteilt mit Parameter

q

, sodass gilt:

E [G] = \frac{1}{q}

.

Der zweite Fall, d.h. die Bestimmung des zugehörigen

q

, ist wesentlich komplizierter und es scheint mir, dass es dazu klassisch nur asymptotische Ergebnisse gibt:
en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model
mathoverflow.net/questions/60075/connectivity-of-the-erd%C5%91s-r%C3%A9nyi-random-graph

Ich kenne aber jemanden, der sich sehr gut mit E-R-Graphen auskennt und werde mal fragen.

Gruß Mauthagoras

klauszi aktiv_icon

10:28 Uhr, 01.08.2017

Wartezeitproblem trifft den Nagel auf den Punkt :-).

Hierzu wollte ich noch mal anmerken, dass die W'keit m Kanten zu erhalten, genau

1

ist, denn es werden aus allen Kanten mit der Anzahl

(\binom{n}{2})

genau

m

gezogen. Aber wie in der Stochastik üblich, kann man ja annehmen, dass nicht

m

gezogen werden, sondern mit W'keit

p = \frac{1}{(\binom{n}{2})}

eine Kante vorhanden bzw. mit

q = 1 - p

nicht enthalten ist. Erwartungstechnisch müssen

m

Kanten resultierenden. (Die Annahme ist dann aber approximativ oder?)

Vielleicht ist noch interessant, dass jeder E-R-Graph genau dann zusammenhängend ist, wenn es einen Teilgraphen

g \subset G

als Baum gibt. Im Prinzip kann man mithilfe der totalen W'keit wie folgt vorgehen:

P (G i s t z u s a m m e n h ä n g e n d) = p * P (G_{+ e} i s t z u s a m m e n h ä n g e n d) +

(1 - q) P (G_{- e} i s t z u s a m m e n h ä n g e n d)

mit

G_{+ e}

als den aus G mit der Verschmelzung der Knoten

v_{1}

und

v_{2}

aus

e = {v_{1}, v_{2}}

resultierender Graph und

G_{- e}

als Graphen der die Kante

e

garantiert nicht enthalten wird.

Dabei gilt

P (G_{+ e}) = 1

, wenn letztlich nur ein Knoten existiert, denn dies würde bedeuten, dass alle Knoten miteinander verschmolzen wurden -> zusammenhängend.Hierzu hab ich auch noch eine Formel gefunden, bzw. jemanden gefunden, der nach der Erklärung der Formel fragt ;-)

math.stackexchange.com/questions/584228/exact-probability-of-random-graph-being-connected

Jetzt besteht nur noch das Problem, dass der Graph im Prinzip nicht zusammenhängend sein muss! Knoten, die keiner Kante zugeordnet wurden, entfallen aus der Zusammenhangsbetrachtung...

Mauthagoras aktiv_icon

10:54 Uhr, 01.08.2017

Okay, für mich ist das Modell mit zufälliger Kantenanzahl üblich. Dann ist mein Fall (i) natürlich nicht relevant und der Algorithmus hat keine zufällige Laufzeit.

Dein letzer Post klingt, als wäre Deine Frage eigentlich viel spezieller als es zuerst klang... Was ich geschrieben habe hat nichts beigetragen, weil Du in Wirklichkeit nur noch wissen möchtest, wie Du mit den entfernten Kanten umgehen kannst. Es wäre schön gewesen, wenn Du das klarer geschrieben hättest.

Kannst Du nochmal die Motivation dafür beschreiben, isolierte Knoten zu ignorieren? Die Aussage, dass sich Deine Analyse auf die Anzahl der Kanten und weniger auf die der Knoten bezieht, wundert mich, da die beiden natürlich stark zusammenhängen. Wäre die Zielfrage "Wie viele (n,p)-ER-Graphen müssen durchschnittlich erzeugt werden, bis einer zusammenhängend ist?", dann könntest Du keine Knoten ignorieren. Was ist also die Zielfrage?

klauszi aktiv_icon

13:05 Uhr, 01.08.2017

Ich hatte heute/gestern als ich den Post geschrieben eine lange Nacht und konnte daher viel recherchieren und überlegen (Nachtmensch). Das Problem mit dem Umgang von isolierten Knoten ist nach der langen Nacht mein letztes Rätsel :-), also als ich die Frage geschrieben habe, hatte ich echt gar kein Plan, was zu tun ist.

So jetzt sehr spezifisch und wiederhole ggf:

Ich habe ein Programm erhalten, welches die Zuverlässigkeit eines Netzes berechnet. Ein Netz besteht aus Knoten und eindeutigen (keine parallelen Kanten), ungerichteten Kanten. Ein Knoten steht für ein Gerät bspw. für einen Computer, ein Server o.ä., eine Kante steht für eine Verbindung zweier Geräte. So ein Graph könnte bpw. wie folgt aussehen:

(a)

(b) ____ (c)

2

mit

G = (V, E)

und

V = {a, b, c}

und

E = {0 = {a, b}, 1 = {a, c}, 2 = {b, c}}

. Hierzu wird jedes Graphenelement eine Intaktwahrscheinlichkeit (I.W.), eine Wahrscheinlichkeitsangabe der Funktionsfähigkeit während einer gegebenen Missionszeit , zugeschrieben. Nehmen wir mal konkret am Beispiel von

G

an, dass alle Knoten garantiert intakt sind, also alle I.W. der Knoten genau 1 sind, und die Kanten mit Wahrscheinlichkeit 0.5 mindestens in einer gegebenen Missionszeit ausfallen. Hierzu könnte eine Zuverlässigkeitkeitsfrage wie folgt lauten: Wie groß ist die Wahrscheinlichkeit, dass während einer Missionszeit die Knoten a und c ununterbrochen in Verbindung stehen?

Die Lösung des Problems lautet trivialerweise:

0 . 5^{1} + 0 . 5^{2} - 0 . 5^{3} = 0.125

, da die Knoten a und b mithilfe der Verbindung (a,0,b) und (a,1,c,2,c) eine intakte Verbindung eingehen können. Das erhaltende Programm gibt genau den selben Wert aus. Erforderlich für den Eingabegraphen ist hierbei, dass das Netz zusammenhängend ist und mindestens zwei Knoten

K \subset V

miteinander eine Verbindung eingehen müssen. Die Vorgehensweise des Programms hängt hierbei sehr stark von der Kantenanzahl ab.

Ein großes Problem des Programms ist die exponentielle Laufzeit (Problem liegt in NP-hard)! Meine Aufgabe lautet: Verbessern Sie das Programm durch einen Preprocessing, der den Eingabegraphen mit wenig Aufwand zugungsten der Zuverlässigkeitsberechnung vor der eigentlichen Berechnung verbessert. Dies habe ich auch getan. Wichtiger Merkmal meines Preprocessing ist es, dass je vernetzter der Graph ist, desto weniger der Laufzeit günstige Veränderungen kann ich am Eingegraphen vornehmen. Wenn es bspw. sehr viele Knoten mit dem Grad 1 oder 2 gibt, desto wahrscheinlicher der Erfolg des Preprocessing.

Nun möchte ich anhand zufälliger erzeugter Graphen die Laufzeit zwischen dem Programm ohne Preprocessing und mit dem Preprocessing vergleichen. Da das Programm sehr stark von der Kantenanzahl abhängt ist meine meine Überlegung:
Wenn ich eine feste Knotenanzahl

m = 20

habe - ein übliches zu untersuchendes Netz ist ein Graph mit bis zu 20 Knoten - dann fange ich mit einem Zufallsgraphen an, der sehr wahrscheinlich nicht stark vernetzt ist und erhöhe langsam die Anzahl der Knoten. Wenn die Anzahl der Kanten bspw. 10 ist, dann ist die Wahrscheinlichkeit relativ hoch, dass ein zusammenhängender E-R-Graph eher eine Kette bildet, anstatt einen vollständigen Graphen. Mit

m = (\binom{20}{2})

wäre die Grenze erreicht,- der Preprocessing ist lediglich ein Overhead für das Programm und demnach ineffizient.

Der Zufallsgraphalgorithmus funktioniert so:

G(n,m)
1a) Erzeuge eine Liste S von allen möglichen Kanten mit n Kanten.
1b) Erzeuge eine leere Kantenliste E
2) m' = m
3) Generiere eine Zufallszahl a von 0 bis m'-1
4) Falls m' 0 ist

, dann teste ob dieser die Kantenliste E zusammenhängt:

Wenn ja, dann gib E aus

Wenn nein, dann verwerfe E und gehe zu 1)

, ansonsten weiter zu 5)
5) Füge die a.te Kante in S zu E, entferne a.te Kante aus S, setze m' = m' -1 und gehe zu 3

Hierzu habe ich jedoch die Überlegung gemacht, was denn passieren würde, wenn ich die Anzahl der Knotenanzahl auf 2000 setze und die Knotenanzahl auf 2 setze? Wie lange müsste ich denn warten, bis ein Zufallsgraph generiert werden würde! Der Erwartungswert ist demnach sehr interessant!

Mauthagoras aktiv_icon

09:20 Uhr, 02.08.2017

Okay, danke.

Allerdings bin ich immer noch skeptisch (vermutlich weil es einfach zu weit führen würde, wenn Du es erklärst), ob es vertretbar ist, isolierte Knoten wegzulassen.

Kleine Zusammenfassung:

Parameter:

n

: Anzahl der Knoten,

m

: Anzahl der Kanten, zwischen

0

und

(\binom{n}{2})

p

: Wahrscheinlichkeit einer Kante.

Es ist doch immer noch so, dass Du solange Graphen der "Größe"

(n, m)

erzeugst, bis einer davon zusammenhängend ist, oder? Dann muss also

m \geq n - 1

gelten und die Zahlenkombination

2

und

2000

in Deinem Beispiel ist nicht möglich.

Wenn wir auf die feste Kantenanzahl

m

verzichten könnten, dann liefert die asymptotische Rate

2 \ln (n) / n

eine gute Beziehung zwischen

n

und

p

, um mit sehr hoher Wahrscheinlichkeit einen zusammenhängenden Graphen zu bekommen, in dem Sinne, dass Du durchschnittlich (wesentlich) weniger als zwei Versuche brauchst, bis der Graph zusammenhängt.
So scheint es auf jeden Fall, wenn ich die Formel, die Du verlinkt hast, berechnen lasse und das asymptotische Resultat selbst ist natürlich eine formale Rechtfertigung.
Konkret: Der Graph ist mit sehr hoher Wahrscheinlichkeit zusammenhängend, falls

p \geq 2 \ln (n) / n

. Das gilt insbesondere, falls

n \geq 4 / p^{2}

. Also für z.B.

p = 0.5

sind

n = 16

Knoten eine gute Wahl.

Für die Variante mit fester Kantenzahl wüsste ich bis jetzt nur sehr informal, wonach man sich richten könnte. Typischerweise würde man versuchen, die folgende naheliegende, heuristische Wahl theoretisch zu rechtfertigen:

n := ⌈ 4 / p^{2} ⌉

und

m := ⌊ ((\binom{n}{2}) + 1) * p ⌋

. Die Motivation für

n

ist die oben genannte und die Motivation für

m

ist, dass dies die wahrscheinlichste Kantenanzahl bei der gewählten Kombination von

n

und

p

ist. Also ist es vernünftig zu erwarten, dass man nur wenige Graphen erzeugen muss. Es fehlt jedoch die theoretische Begründung.

Noch eine kleine Bemerkung: Dein Verfahren, ohne Zurücklegen

m

aus den möglichen

(\binom{n}{2})

Kanten zu ziehen, erscheint mir sehr umständlich. Typische Sprachen wie R und MatLab können das einfach so.

Ich hoffe, das war jetzt nicht zu verwirrend geschrieben...

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1382171

1382092

	Status: nicht eingeloggt	Noch nicht registriert?