planare Graphen mit 6 Ecken < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:35 So 09.01.2011 | | Autor: | Scharii |
| Aufgabe | Es sei Z ein zufällig ausgewählter Graph aus der Menge der einfachen Graphen mit genau 6 Ecken.
Es sei P die Wahrscheinlichkeit, dass Z planar ist.
Berechnen sie:
P [mm] \geq \frac{27814}{32768} [/mm] , P< [mm] \frac{32637}{32768}
[/mm]
Hinweis: Betrachten sie die Fälle dass Z genau k Kanten hat für k=0...9 und k=13...15 |
Hi,
also, oben steht die Aufgabe.
Die Frage ist, wie komme ich genau drauf dass ich planare Graphen hab.
Ich weiss, wenn nur 4 Ecken mit Kanten verbunden werden ist der Graph auf jeden Fall planar [mm] (K_4 [/mm] ist planar)
Wenn ich noch mehr Ecken nehme kann der Graph planar werden, muss er aber nicht - wie unterscheide ich das dann gut? Und wie genau zähle ich die.
Steh grad irgendwie auf dem Schlauch, ich hoffe ihr könnt mir helfen die Aufgabe zu lösen :)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:13 So 09.01.2011 | | Autor: | Scharii |
Meine Idee ist jetzt erstmal einen vollen [mm] K_6 [/mm] zu bauen (15 Kanten), dann eine Kante entfernen, schauen ob der Graph planar ist oder nicht, und so die nicht-planaren Graphen zu zählen.
Mein Problem ist zu entscheiden, ob ein Graph planar ist (zu viele Einzelfälle zum testen), einen einfachen Algorithmus hab ich dazu nicht gefunden, sodass mein Rechner das Zählen auch nicht abnehmen kann.
Kann mir da jemand beim Zählen helfen?
Meine Wahrscheinlichkeit P ist ja dann zum Ende:
[mm] \frac{15! - (Anzahl der nicht-planaren Graphen)}{15!}
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:57 Mo 10.01.2011 | | Autor: | Scharii |
Hab die Aufgabe jetzt gelöst.
Betrachtung der Kanten hat mich weitergebracht, es gibt aber nur
[mm] \summe_{i=1}^{15}\vektor{15 \\ i}=2^{15} [/mm] verschiedene Graphen, nicht 15! .
Graphen mit weniger als 9 Kanten können nur planar sein
(Kuratowski), und nur einer mit 9 Kanten ist nicht planar (genau der [mm] K_{3,3}).
[/mm]
Andersrum kann kein Graph mit mehr als 12 Kanten planar sein, da jeder mindestens den [mm] K_{3,3} [/mm] enthält (Eckengrad überall grösser gleich 3).
Damit kann man das P genug einschränken. (Wenn man noch ein paar nicht-planare mit 10,11 oder 12 Kanten findet, aber das geht auch).
Mein grösster Fehler war am Anfang nicht den Binomialkoeffizienten zu verwenden, da hab ich mich gründlich verzählt ^^
|
|
|
|
