| Autor |
 Zufallsgraph fast immer np^2/2-zusammenhängend |
|
Aimbot
Aktiv 
Dabei seit: 04.03.2013
Mitteilungen: 85
 |
Hallo,
ich muss folgende Aufgabe zeigen:
Für jedes $0 < p < 1$ gilt: $\lim_{n->\infty} P(G(n,p)$ ist $\frac{np^2}{2}$-knotenzusammenhängend$)=1$.
Habe aber leider keine gute Idee was ich machen kann. Das Ganze ist im Zusammenhang mit dem Lovasz-Local-Lemma und der Chernoff-Ungleichung. Leider weiß ich nicht wie eins von den beiden mir dabei helfen kann.
Ich wollte das ganze ähnlich zeigen wie für den Fall, dass p und k konstant sind, wie hier: math.stackexchange.com/questions/1043008/proof-for-k-connectedness-of-random-graphs
Aber das funktioniert leider nicht, da die Abschätzung immer gegen Unendlich läuft.
Kann mir da jemand helfen?
|
 Notiz  Profil
 Quote
 Link |
Delastelle
Senior 
Dabei seit: 17.11.2006
Mitteilungen: 1601
 |      Beitrag No.1, eingetragen 2020-12-06
|
Hallo Aimbot!
Ich überblicke die Aufgabe bisher nicht so richtig...
Aber: ich würde eventuell mit einem kleinen Graph anfangen und falls ich etwas erkenne zu größeren Graphen übergehen!
Viele Grüße
Ronald
|
Notiz Profil
Quote
Link |
Aimbot
Aktiv
Dabei seit: 04.03.2013
Mitteilungen: 85
| Beitrag No.2, vom Themenstarter, eingetragen 2020-12-06
|
Ich habe eine Idee, wo ich aber irgendwo einen Denkfehler haben muss... Ich nutze nur die Wahrscheinlichkeit aus, dass Wege der Länge 2 existieren.
Wahrscheinlichkeit, dass fester Weg der Länge 2 zwischen zwei Knoten existiert: $p^2$
Anzahl mögliche Wege der Länge2 zwischen zwei festen Knoten: $n-2$
Wahrscheinlichkeit, dass keine $\frac{np^2} 2$ Wege der Länge 2 zwischen zwei festen Knoten existieren: $(1-p^2)^{n-2-\frac1 2 np^2}$
Wahrscheinlichkeit, dass ein Knotenpaar existiert, für das keine $\frac{np^2} 2$ Wege der Länge 2 existieren:
$\binom n 2 (1-p^2)^{n-2-\frac1 2 np^2} \rightarrow 0$ für $n \rightarrow \infty$.
|
Notiz Profil
Quote
Link |
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1601
| Beitrag No.3, eingetragen 2020-12-08
|
Hallo Aimbot!
Mir ist nicht klar was ein Zufallsgraph sein soll!
- 2D / 3D
- eben ja/nein
- wo liegen Knoten
- Wahrscheinlichkeit für Kanten
- ...
Viele Grüße
Ronald
|
Notiz Profil
Quote
Link |
Aimbot
Aktiv
Dabei seit: 04.03.2013
Mitteilungen: 85
| Beitrag No.4, vom Themenstarter, eingetragen 2020-12-08
|
Es geht sich um den Erdos Renyi Zufallsgraphen, d.h. es gibt n Knoten und es gibt mit der Wahrscheinlichkeit p eine Kante zwischen jeweils zwei Knoten.
Meine Lösung ist falsch, da beim Löschen eines Knotens bis zu n-3 Wege der Länge 2 zerstört werden können. Aber ich habe bisher noch keine gute Idee wie man das sonst angehen kann.
|
Notiz Profil
Quote
Link |
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1601
| Beitrag No.5, eingetragen 2020-12-08
|
Hallo,
eventuell kann man mal versuchen:
vollständige Induktion über die Knotenzahl (wenn die immer größer werden soll)
Viele Grüße
Ronald
|
Notiz Profil
Quote
Link |
Aimbot
Aktiv
Dabei seit: 04.03.2013
Mitteilungen: 85
| Beitrag No.6, vom Themenstarter, eingetragen 2020-12-08
|
Das bringt ja nichts, ich will es ja nur für n-> unendlich zeigen, mit deiner Idee müsste ich eine noch stärkere Aussage zeigen: Ich muss auch noch ein N finden, sodass es für jedes n>N gilt. Aber danke für die Hilfe.
|
Notiz Profil
Quote
Link |
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
