matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieAnfänger: Random Graphs
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Graphentheorie" - Anfänger: Random Graphs
Anfänger: Random Graphs < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Anfänger: Random Graphs: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 23:33 Mo 19.06.2006
Autor: MichaelNorman

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.

        
Bezug
Anfänger: Random Graphs: Antwort
Status: (Antwort) fertig Status 
Datum: 08:21 Di 20.06.2006
Autor: mathiash

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

Bezug
                
Bezug
Anfänger: Random Graphs: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Anfänger: Random Graphs: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
Anfänger: Random Graphs: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Anfänger: Random Graphs: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:10 Di 20.06.2006
Autor: MichaelNorman

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

Bezug
                        
Bezug
Anfänger: Random Graphs: Antwort
Status: (Antwort) fertig Status 
Datum: 16:17 Di 20.06.2006
Autor: mathiash

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

Bezug
                                
Bezug
Anfänger: Random Graphs: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:12 Di 20.06.2006
Autor: MichaelNorman

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

Bezug
                                        
Bezug
Anfänger: Random Graphs: Antwort
Status: (Antwort) fertig Status 
Datum: 08:18 Mi 21.06.2006
Autor: mathiash

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.


Bezug
                                                
Bezug
Anfänger: Random Graphs: Dankes schön
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:13 Do 22.06.2006
Autor: MichaelNorman

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

Bezug
        
Bezug
Anfänger: Random Graphs: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:20 Mi 28.06.2006
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]