Graphentheorie

Neue Frage »

Ana_Ana Auf diesen Beitrag antworten »
Graphentheorie
Hallo zusammen,
ich muss in der Graphentheorie ein Seminararbeit schreiben. Es handelt sich um Zufallsgraphen. Ich hoffe Ihr könnt mir helfen.Ich blicke nicht mehr durch.
Die Fragen lauten:

1.Mit welcher Wahrscheinlichkeit hat ein Graph mit n Ecken eine
vorgegebene Taille?
2.Welche Taille erwarten wir bei einem zufallig gewahlten Graphen aus
G4; 1/2(4 ecken mit kantenwahrscheinlichkeit p)

Zu1&2: Ich ich will es für n=4; und p=1/2 versuchen.

Ich konnte bis jetzt nur es zeichnen und habe herausefunden dass es insgesamt 32 taille länge 3 gibt. und 11 länge 4(also eher kreise, taille kann man die nicht mehr nennen) ich finde nirgendwo ein formel um es zu berechnen.Um den Erwartungswert zu berechnen muss ich doch anzahl taille (3)/64 graphen *3+ anzahl taille (4)/64 *4 oder??
aber wie finde ich wie viele taillen länge 3 gibt? Ich dachrte am anfang kann ich einfach die erwarten anzahl von kreisen länge 3 nehmen aber das ist leider falsch.

Ich habe leider keine Ahnung mehr wie ich das lösen könnte.
Bis jetzt habe ich die Formel herausgefunden dass es n!/(n-k)! * n/(n+1) anzahl Taille Länge 3 gibt. aber bin mir nicht sicher. also die erste hälfte der Formel wäre Anzahl der Kreise Länge 3 aber die Zweite weiss ich nicht was das bedeutet. Ich habe herumprobiert und es so hinzugefügt das das Ergebniss stimmt.

HIlFEEE
Könnt Ihr mir da helfen vieleicht??
Liebe Grüsse
Ana
Abakus Auf diesen Beitrag antworten »
RE: Graphentheorie
Hallo!

Zitat:
Original von Ana_Ana
1.Mit welcher Wahrscheinlichkeit hat ein Graph mit n Ecken eine
vorgegebene Taille?
2.Welche Taille erwarten wir bei einem zufallig gewahlten Graphen aus
G4; 1/2(4 ecken mit kantenwahrscheinlichkeit p)

Zu1&2: Ich ich will es für n=4; und p=1/2 versuchen.


Mir sind einige der Begriffe hier fremd, was zB ist eine Taille? Was ist die Kantenwahrscheinlichkeit?

Grüße Abakus smile

PS: willkommen im Board Wink
Ana_Ana Auf diesen Beitrag antworten »

Hallo Abakus,
danke für die Antwort.

Also die Taille ist der kürzeste Kreis in einem Graphen.
Und mit Kantenwahrscheinlichkeit p=1/2 ist hier die Wahrscheinlichkeit dass eine Kante autritt. hier tritt eine bestimmte Kante mit 50 % ein und mit (1-p)=1/2 also 50 %tritt sie nicht ein.

Ein Graph mit 4 Ecken kann maximal n*(n-1)/2 Kanten haben also 6
Ich kann zum Beispiel aus 4 Ecken 64 graphen bilden. Weil 6über 0(also graphen mit 4 ecken und 0 kanten oder anders gesagt von 6 möglichen Kanten kommen 0)=1 + 6über 1=6; + 6 über 2 und so weiter bis 6 über 6. als Endergebnis bekomme ich dann 64.
Ich will wissen wie viele von diesen Graphen eine Taille Länge 3 haben. Der kürzeste Kres den Sie beeinhalten sollte der Länge 3 sein

Die formel für die Erwartete Anzahl der Kreise eine Bestimmte Länge ist (n!/((n-k)!*2k))* p ^2. Ein Graph kann mehrere Kreise länge 3 haben aber nur 1 Taille. Das heisst die Existenz mehrere Kreise Läng 3 heisst nur dass diese Graph eine Taille Länge 3 hat.

Noch dazu habe ich das Anzahl der Hamilton kreise in einem Graphen mit n vorgegebene Ecken und Kantenwahrscheilichkeit ist (n-1)!/2.
Ich kann aber die Anzahl der Graphen mit Taille länge 3 nicht finden.

Die Graphen die weniger als 3 kanten haben kann ich schon mal ausschliessen da der Kürzeste Kreis 3 kanten hat.

Ich kann die allle Zeichnen. und ich bekomme 32 kreise länge 3 ( kann sich mit der formel auch errechnen in dem man die Erwartungswert erst rechnet und dann mit 64 multipliziert.
Ich kann herausfinden mit den gleichen Formel dass es 12 Kreise länge 4 gibt.
Ich kann auch herausfinden dass es 3 Hamiltonkreise gibt.(die fallen auch schon mal raus weil ein Hamiltonkreis hat die Länge seine Kanten und kann keinen zusätzlichen kreis kürzere Länge haben.

Ich kann durch Zeichnuggen herausfinden dass es 23 Grafen gibt dass eine Taille 3 haben. und nur 3(Hamilton) die Länge 4 haben. aber ich kann das alles irgendwie nicht miteinander verbinden damit ich die 23 von ein Formel bekommen kann.

Ich hoffe Du kannst mir da weiterhelfen.
Gruss
Abakus Auf diesen Beitrag antworten »

Auf die 23 komme ich auch, ja. Ich unterscheide einfach die verschiedenen Fälle:

- Graphen mit 0, 1, 2 Kanten haben keine solche 3-Taille,

- bei Graphen mit 3 Kanten, die 3 Knoten verbinden, gibt es - viele Möglichkeiten

- bei Graphen mit 4 Kanten kommt (gegenüber einem mit 3 Kanten) noch jeweils eine beliebige Kante hinzu, dazu gibt es insgesamt 3 Möglichkeiten pro Graph; macht insgesamt - viele Möglichkeiten

- bei Graphen mit 5 Kanten gibt es 6 Möglichkeiten (beim vollständigen Graph hast du 6 Möglichkeiten, eine Kante wegzulassen)

- und zuletzt gibt es noch einen Graphen mit genau 6 Kanten

Das macht insgesamt: 4 + 12 + 6 + 1 = 23

Die 23 lässt sich demnach noch erklären, eine Verallgemeinerung auf beliebige Graphen dürfte kniffliger sein.

Grüße Abakus smile
Ana_Ana Auf diesen Beitrag antworten »

Hallo Abakus,
Ich danke dir für deine Antwort.
In der Tat suche ich eine allgemeine Lösung zu der Problem.
Ich habe auch eine Lösung gefunden aber leider nicht allgemein:
für k<3 Keine Graphen mit der Taille drei
für k =3 6 über 3 - Anzahl aufspannende Bäume
für k=4 6 über 4 minus Anzahl der Hamilton Kreise
für k >4 alle minus bipartiten Graphen
Aber ich hätte doch ein Paar Fragen zu deine Lösungsansatz wenn ich darf
Du sagst:
bei Graphen mit 3 Kanten, die 3 Knoten verbinden, gibt es - viele Möglichkeiten - bei Graphen mit 4 Kanten kommt (gegenüber einem mit 3 Kanten) noch jeweils eine beliebige Kante hinzu, dazu gibt es insgesamt 3 Möglichkeiten pro Graph; macht insgesamt - viele Möglichkeiten - bei Graphen mit 5 Kanten gibt es 6 Möglichkeiten (beim vollständigen Graph hast du 6 Möglichkeiten, eine Kante wegzulassen) - und zuletzt gibt es noch einen Graphen mit genau 6 Kanten

Frage 1: woher weiss du dass es bei 4 Kanten gegenüber 3 Kanten 3 Möglichkeiten dazu gibt eine Kante dazu zu setzen?
Frage 2: wie kommst du zu der Formel 4 über 3 Graphen mit der taille 3??

Ich danke dirsmile
Viele Grüsse
Ana
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von Ana_Ana
Frage 1: woher weiss du dass es bei 4 Kanten gegenüber 3 Kanten 3 Möglichkeiten dazu gibt eine Kante dazu zu setzen?
Frage 2: wie kommst du zu der Formel 4 über 3 Graphen mit der taille 3??


Ich wähle 3 Knoten aus, die untereinander verbunden sind. Das ist eine Kombination ohne Wiederholung, d.h. es gibt - viele Möglichkeiten von Graphen mit Taille 3 und 3 Kanten bei 4 Knoten. Dadurch ist die 3-er Taille festgelegt, die restliche Kante kann beliebig verteilt werden: 3 Kanten sind noch frei, von denen genau eine ausgewählt werden kann.

Leider funktioniert es nicht, diese Idee (auf Graphen mit n Knoten) zu verallgemeinern, aber es reicht für eine Abschätzung. Vielleicht bringt es dich ja auf weitere Ideen:



Grüße Abakus smile
 
 
Ana_Ana Auf diesen Beitrag antworten »

Hallo Abakus,
Danke nochmal für deine Antwort und Geduld.
Jetzt habe ich es verstanden was du meinst.
Deine Formel habe ich auch getestet. Also wenn mann k 3 4 5 und 6 einsetzt bekommt man ein Ergebnis von 32. In der Tat das ist die Anzahl der kreise Länge 3 bei 4 Ecken und eine Kantenwarhscheinlichkeit von 1/2.
Sagt aber momentan nichts zu der Graphen mit Taille 3.
Habe versucht damit rumzuspielen aber bin zu keine Ergebniss gekommen. unglücklich
Trotzdem danke für deine Hilfe.
Finde ich sehr nett.

Grüsse
Ana smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »