Planare Graphen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 05:46 Do 03.01.2013 | | Autor: | mmaths |
| Aufgabe | | Gibt es einen planaren Graphen mit 7 Knoten und 22 Kanten? |
Zur Aufgabe 1: Ich würde hier die Formel Kanten(G) <= 3 * Knoten(G) - 6 nehmen.
Eingesetzt in die Ungleichung ergibt sich:
22 <= 3*7 - 6
22 <= 15
Somit hätte ich die nicht-planarität bewiesen. Was ist aber, wenn Zahlen gegeben sind, sodass das die Ungleichung aufgeht.
Wie müsste man in dem Falle argumentieren? Immerhin gibt es ja Graphen wie den Petersen-Graph, wo die Ungleichung aufgeht, aber es sich trotzdem nicht um einen planaren Graphen handelt?
Prinzipiell fällt es mir schwer, nicht-planarität nachzuweisen. Wenn ich beispielsweise auf Grund eines Schaubildes mehrere überschaubare Graphen habe (ca. 10 Knoten und max 20 Kanten), wie weiße ich es dort am besten nach? Denn mir fällt es Schwer, einen K5 oder K3,3 so einfach zu erkennen. Auch habe ich keine Quelle gefunden, die das Vorgehen in einem solchen Fall erklärt.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Gibt es einen planaren Graphen mit 7 Knoten und 22 Kanten?
> Zur Aufgabe 1: Ich würde hier die Formel Kanten(G) <= 3 *
> Knoten(G) - 6 nehmen.
>
> Eingesetzt in die Ungleichung ergibt sich:
> 22 <= 3*7 - 6
> 22 <= 15
>
> Somit hätte ich die nicht-planarität bewiesen. Was ist
> aber, wenn Zahlen gegeben sind, sodass das die Ungleichung
> aufgeht.
>
> Wie müsste man in dem Falle argumentieren? Immerhin gibt
> es ja Graphen wie den Petersen-Graph, wo die Ungleichung
> aufgeht, aber es sich trotzdem nicht um einen planaren
> Graphen handelt?
>
> Prinzipiell fällt es mir schwer, nicht-planarität
> nachzuweisen. Wenn ich beispielsweise auf Grund eines
> Schaubildes mehrere überschaubare Graphen habe (ca. 10
> Knoten und max 20 Kanten), wie weiße ich es dort am besten
> nach? Denn mir fällt es Schwer, einen K5 oder K3,3 so
> einfach zu erkennen. Auch habe ich keine Quelle gefunden,
> die das Vorgehen in einem solchen Fall erklärt.
Hallo mmaths,
Die allgemeine Charakterisierung der Eigenschaft "Planarität"
ist nicht ganz einfach zu erfassen. In Wikipedia steht etwa:
Die Planarität eines Graphen lässt sich mit verschiedenen
Algorithmen in linearer Zeit testen. Allerdings sind diese
Algorithmen nicht einfach zu implementieren.
(http://de.wikipedia.org/wiki/Planarer_Graph)
Vielleicht findest du gewisse Hilfen im Dokument,
welches in Google unter
"Skript: Algorithmen für planare Graphen - Algorithmik I - Karlsruher ..."
erscheint.
Dort steht allerdings auch:
Ein Algorithmus, der basierend auf der Aussage dieses
Satzes für einen beliebigen Graphen untersucht, ob
dieser planar ist, würde Subgraphen betrachten, und
entscheiden, ob diese Unterteilungen des K3;3 oder K5
sind. Es gibt mindestens [mm] 2^m [/mm] Subgraphen. Dieses
Verfahren scheint also nicht effizient zu sein.
Man könnte anhand des Beweises einen effizienten
Algorithmus angeben. Es gibt verschiedene effiziente
Algorithmen zum Testen auf Planarität mit Laufzeit O(n),
siehe Kapitel ??.
(man beachte die Konjunktive "würde" und "könnte"
sowie der Verweis auf ein "Kapitel Nr. ??" ... )
So wie ich sehe, wäre wohl der Algorithmus nach
Boyer/Myrvold (2004) der gegenwärtige Standard für
dieses Thema.
Betrachte z.B. die Slide-Show, die bei Google unter der
Kurzüberschrift "v" auf das Stichwort "Boyer Myrvold" erscheint:
![[]](/images/popup.gif) Slide Show Boyer Myrvold
LG Al-Chwarizmi
|
|
|
|
