Anfänger: Random Graphs < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo an alle.
Ich suche gerade einen Einstieg in die Graphentheorie, mit einer Frage, die für Profis sicher einfach ist, ich stehe aber gearde etwas vorm Berg. Ich habe einen gerichteten Zufallsgraphen (nach Gilbert, n Knoten, m Kanten, zwei Knoten sind mit einer Wahrscheinlichkeit von p verbunden), und hätte gerne die Wahrscheinlichkeit, dass irgend zwei Knoten miteinander über bis zu k Kanten verbunden sind, also ob zwischen zwei Knoten eine Verbindung bis zu einer gewissen Tiefe besteht. Wie komme ich da ran? Muss ich das über Wahrscheinlichkeitsverteilungen machen? Oder welche Wege gibt es.
Danke für eure Hilfe,
viele Grüße,
Norman
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo und guten Morgen,
mir fällt momentan nur ein, das zu Fuß zu rechnen. Vorab Literatur: Im Buch Graph Theory von B. Bollobas steht ein Kapitel ueber
Random Graphs, ausserdem gibt es ein Standard-Buch (Erdös-Spencer ???) mit Titel ''Random Graphs''.
Ich würd also
[mm] P_k:=Pr(verbunden [/mm] über genau k Kanten und nicht über <k Kanten) ausrechnen:
[mm] P_1 [/mm] = p
[mm] P_2= (1-p)\cdot \sum_{l=0}^{n-3}(1-p)^l\cdot p\: =\: (1-p)\cdot p\cdot \frac{1-(1-p)^{n-2}}{1-(1-p)}\: =\: (1-p)\cdot (1-(1-p)^{n-2})
[/mm]
[mm] P_3= [/mm] Pr(es gibt keinen Pfad der Länge 2 von i nach j, aber einen Pfad der Länge 3)
usw. rechnen, zugegeben: Richtig schön ist das nicht.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:36 Di 20.06.2006 | | Autor: | kretschmer |
!!! ACHTUNG: Fehlerhaft !!!
Hallo Ihr beiden,
also ich habe mir das mal durch den Kopf gehen lassen und dachte zuerst, es wäre eventuell nicht zu kompliziert, ich habe einen Vorschlag, bin mir nur nicht sicher, ob das so schon stimmt:
Die Idee ist, das ganze als rekursive Formel aufzuschreiben:
also
[mm] $p_1=p$
[/mm]
dann ist [mm] $p_2$ [/mm] die Wahrscheinlichkeit, dass erstmal es keinen Pfad der Länge [mm] $p_1$ [/mm] gibt, d.h. [mm] $(1-p_1)$ [/mm] mal der Wahrscheinlichkeit für einen Pfad der Länge zwei:
[mm] $p_2=(1-p_1)\vektor{n-2\\1}p^2$
[/mm]
[mm] $\vektor{n-2\\1}$, [/mm] weil man genau einen Knoten zwischen den beiden anordnen kann, um auf die entsprechende Länge zu kommen.
dann für [mm] $p_3$ [/mm] die Wahrscheinlichkeit, dass weder ein Pfad der Länge 1 noch 2 existiert. Das müsste ja [mm] $(1-p_1-p_2)$ [/mm] sein. Dazu kommt noch die Anzahl der Möglichkeiten zwei Knoten dazwischen zu nehmen und das ein entsprechender Pfad existiert:
[mm] $p_3=(1-p_1-p_2)\vektor{n-2\\2}p^3(1-p)^2$
[/mm]
Die [mm] $(1-p)^2$ [/mm] kommen meiner Meinung nach hinzu, da man ja keine falschen Kanten haben darf, d.h. eine Kante von dem 1. Knoten zu dem 3. Knoten der vier Knoten und so einen Pfad der Länge 2 wieder hätte.
Allgemein komme ich dann auf
[mm] $p_k=\left(1-\sum_{i=1}^{k-1}p_k\right)\vektor{n-2\\k-1}p^k(1-p)^{(k-2)(k-1)}$
[/mm]
Der Term [mm] $(1-p)^{(k-2)(k-1)}$ [/mm] kann man sich darüber überlegen, für jeden der Knoten zwischen dem Start und Endknoten darf dieser nicht mit $(k-2)$ verbunden werden. Er hat ja genau zwei Nachbarn und es gibt ausser ihm genau $k$ Knoten.
Vielleicht hilft das irgendwem irgendwie weiter. Aber ich habe weder eine formale Begründung/Beweis dazu jetzt, noch bin ich mir sicher, ob die Formel stimmt. Oder anders ausgedrückt: den Korrektheitsbeweis überlasse ich dem geneigten Leser 
--
Gruß
Matthias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:49 Di 20.06.2006 | | Autor: | just-math |
Hallo ihr alle,
kann es sein, dass kretschmer übersieht, dass die Ereignisse nicht unabhängig sind ?
Viele Grüsse
just-math
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:56 Di 20.06.2006 | | Autor: | kretschmer |
Hallo just-math,
also, da hast Du einfach nur recht! Das habe ich wirklich. Wenn ich das so genauer betrachte, ist das ganze vom Gefühl her auch ansonsten nicht 100% in Ordnung. Hmm. Habe das Gefühl [mm] $p_k$ [/mm] könnte größer als 1 werden und das sollte es ja nicht.
Aber vielleicht kann irgendwer das korregieren, wenn irgendwas daran wenigstens ein brauchbarer Ansatz ist?
--
Gruß
Matthias
|
|
|
| |
|
Hallo Mathias.
Vielen Dank für deine schnelle Antwort. Allerdings weiß ich nicht, ob dein Ansatz stimmen kann, denn wenn ich mal eine Beispielrechnung damit durchführe, komme ich auf sehr hohe Werte. Beispiel:
Gegeben ist ein Graph mit 100 Knoten (n), mit Wahrscheinlichkeit p=0,05 wird zwischen jedem Knotenpaar eine Kante eingefügt. Laut deiner Formel [mm] (1-p)*(1-(1-p)^n-2) [/mm] würde ich eine Wahrscheinlichkeit von über 0,9 für einen Pfad der Länge 2 bekommen. Oder habe ich etwas komplett falsch verstanden??
Ich werde erstmal weiter suchen, bin gerade auf die Begriffe STCON und Erreichbarkeitsproblem gestoßen, allerdings weiß ich noch nicht, ob ich daraus etwas für meinen speziellen Fall ziehen kann.
Viele Grüße,
Norman
|
|
|
| |
|
Moin nochmal,
also p=0.05 und n=100 liefert für zwei fixierte Knoten i,j
Pr(Pfad der Länge 2 und keiner der Länge 1 zw. i und [mm] j)=(1-0.05)\cdot \sum_{k=1}^{98} (1-0.05)^{k-1}\cdot [/mm] 0.05
= [mm] 0.95\cdot 0.05\cdot \frac{1-0.95^{99}}{1-0.95}
[/mm]
= [mm] 0.95\cdot (1-0.95^{99}) [/mm]
Gruss,
Mathias
|
|
|
| |
|
Hallo Mathias.
Dann habe ich das ja richtig verstanden, allerdings kommt mir das Ergebnis, also die Wahrscheinlichkeit, dass zwei Knoten über eine Pfad der Länge 2 verbunden sind, sehr hoch vor.
0,95*(1-0,95^99) = 0,944
Das heisst ja, dass ich mit über 94% Wahrscheinlichkeit zwischen zwei Knoten einen Pfad der Länge 2 habe. Ist das realistisch? Ich bin (wie ihr sicher schon gesehen habt...:)) mit Statistik nicht sehr vertraut...
Gruß, Norman
|
|
|
| |
|
Hallo nochmal,
warum denn nicht ? Die Wahrscheinlichkeit ist ja 1 - die Wahrsch., dass kein solcher Pfad existiert, und das ist sowas wie
[mm] 0.95^{2\cdot 98}, [/mm] was halt schon recht klein ist - und auch als recht klein vorstellbar.
Gruss,
Mathias
ps Was halt immer noch fehlt, ist die allgemeine Formel. Falls mir noch was dazu einfällt, werd ich nochmal schreiben.
|
|
|
| |
|
Super, danke dir Mathias. Ich bin auch noch fleissig am suchen, wenn ich was finde, werde ich es hier posten. Schönen Tag noch, Grüße,
Norman
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:20 Mi 28.06.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
