Beweis des Satz von Kuratowski < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo!
Ich versuche gerade den Beweis zum Satz von Kuratowski zu verstehen und hoffe auf eure Hilfe.
Kuratowskis Satz:
Ein Graph ist genau dann planar, wenn er keine Unterteilung von [mm] $K_5$ [/mm] oder [mm] $K_{3,3}$ [/mm] als Subgraph enthält.
Hier ein Teil des Beweises (Auszug aus dem Skript von Prof. Wagner am Karlsruher Institut für Technologie[0]):
Wir haben bereits gezeigt, dass [mm] $K_5$ [/mm] und [mm] $K_{3,3}$ [/mm] nicht planar sind. Damit ist klar, dass ein planarer Graph keine Unterteilung des [mm] $K_5$ [/mm] bzw. [mm] $K_{3,3}$ [/mm] als Subgraph enthalten kann. Es bleibt zu zeigen, dass jeder Graph, der keine Unterteilung des [mm] $K_5$ [/mm] bzw. [mm] $K_{3,3}$ [/mm] als Subgraph enthält, planar ist.
Wir führen eine Induktion über die Anzahl n der Knoten des Graphen $G = (V, E)$ durch. Für $n [mm] \le [/mm] 4$ gilt die Behauptung, da [mm] $K_4$ [/mm] planar ist. Für $n [mm] \ge [/mm] 5$ führen wir eine Induktion über die Anzahl m der Kanten des Graphen durch.
Wenn der Graph $m = 0$ Kanten enthält, ist G trivialerweise planar. Gelte also die Behauptung für alle Graphen mit weniger als n Knoten oder n Knoten und echt weniger als m Kanten. $G = (V,E)$ sei ein Graph mit $|V| = n [mm] \ge [/mm] 5$ und $|E| = m$. Wir machen eine Fallunterscheidung nach [mm] $\kappa(G)$.
[/mm]
Den kompletten Beweis findet man im Skript[0] ab Seite 16ff.
Ich verstehe den Fall 1 und 2 für [mm] $\kappa(G) [/mm] = 0$ bzw. [mm] $\kappa(G) [/mm] = 1$. Kann jedoch die anderen Fälle nicht nachvollziehen. Evtl. hat jemand einen anschaulicheren Beispiel oder kann den Beweis für Fall 3 und 4 besser erklären?
[0]: http://i11www.iti.uni-karlsruhe.de/_media/teaching/sommer2009/planargraphs/vorlesung.pdf
Freundliche Grüße
Thorsten
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Di 27.08.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
