Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Zufallsgraph fast immer np^2/2-zusammenhängend
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Zufallsgraph fast immer np^2/2-zusammenhängend
Aimbot
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2013
Mitteilungen: 85
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-12-05


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?



Wahlurne Für Aimbot bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1596
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Wahlurne Für Delastelle bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Aimbot
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2013
Mitteilungen: 85
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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$.



Wahlurne Für Aimbot bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1596
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Wahlurne Für Delastelle bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Aimbot
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2013
Mitteilungen: 85
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Wahlurne Für Aimbot bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1596
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Wahlurne Für Delastelle bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Aimbot
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2013
Mitteilungen: 85
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Wahlurne Für Aimbot bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Aimbot hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]