Planare Graphen (Darstellung) | Graphentheorie

Aufrufe: 619     Aktiv: 27.11.2020 um 10:20
0

Ich habe folgendes Problem bei der Planaritätsfeststellung eines Graphen.

Gegeben sei: K_5 (also 5 Knoten), anhand der Euler'schen Polyederformel Alpha 1 (Kanten) < 3 * Alpha 0 (Knoten) - 6 ist festzustellen, ob der Graph planar ist.

Was ich weiß ist, dass der Graph K_5 5 Knoten hat => Alpha 1 (Kanten)  < 3 * 5 - 6

=> also müsste der Graph < 9 Kanten haben => zeichnet man sich den K5 auf wie ein Fünfeck (jeder Knoten hat somit einen Knotengrad von 2 ) (ungerichtet daher Handschlaglemma Knotengrad (10)/ 2 = 5 ) wäre die Polyederformel erfüllt. 5 < 3*5 - 6

Meine Frage... wo steht nun, dass der Graph K5 wie in dem angeführten Link https://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Graph_K5.svg/768px-Graph_K5.svg.png zu zeichnen ist? Man könnte ja theoretisch auch eine Kante beispielsweise weglassen, oder zwei, solange er zusammenhängend bleibt, könnte er planar sein => und bleibt trotzdem ein K_5 Graph.

 

Danke schon mal für eure Antworten :)

Diese Frage melden
gefragt

Auszubildender, Punkte: 148

 
Kommentar schreiben
1 Antwort
0
Hallo, hier ist die Definition eines planaren Graphs: Ein Graph heißt planar falls er in einer Ebene so gezeichnet werden kann, dass sich die Verbindungslinien (Kanten) nicht kreuzen. Der vollständige K5-Graph (sowie gezeichnet in deinem Link, also mit 10 Kanten) ist nicht planar, wenn du aber eine Kante weg nimmst, dann wird er planar (9 Kanten, Eulersche Formel erfüllt). Er ist aber kein K5-Graph mehr, das ist einfach ein Graph mit 5 Knoten (Definition von vollständigen Graphen K1,K2,K3,K4,K5,...). Der K5-Graph ist fast planar, da er durch Entfernung einer seiner Kante planar wird. Das Kuratowski Theorem über planare Graphen könnte dir dabei helfen. Gruß Elayachi Ghellam
Diese Antwort melden
geantwortet

Elektrotechnik Ingenieur, Punkte: 1.49K

 

Kommentar schreiben