Kann ich mit der Eulers Polyeder-Formel herausfinden, ob ein Graph planar ist?

Question

Wir haben heute ebene und planare Graphen angeschaut. Jetzt habe ich etwas nicht ganz verstanden. Zuletzt haben wir die Eulers Polyeder Formel angeschaut, bei einem ebenen Graphen. Kann ich mit der Eulers Polyeder-Formel herausfinden, ob ein Graph planar ist?

v= die Anzahl der Knoten vom Graphen
k= die Anzahl der Kanten vom Graphen
f=die Anzahl der Fläche vom Graphen

v - k + f = 2

Vielen Dank im Voraus!

MfG
Lenovo

Comments

Kann ich mit der Eulers Polyeder-Formel herausfinden, ob ein Graph planar ist?

Nein, leider nicht. Das ist ein notwendiges, aber kein hinreichendes Kriterium. Vorteil: Graphen, die das nicht erfüllen, können nicht planar sein. Nachteil: Erfüllt der Graph die Gleichung, dann heißt das noch nicht, dass er planar ist.

Answer 1

f=die Anzahl der Fläche vom Graphen

Was soll das sein wenn der Graph nicht planar ist?

Comments

oswald

Das wären hier die blauen Punkte, wenn man den Graphen aufzeichnet. (Knoten: schwarze Punkte, Kanten: rote Striche)

Vielen Dank im Voraus!

MfG
Lenovo

---

Der Graph, den du gezeichnet hast, ist planar. Wie man in einer planaren Einbettung des Graphen in die Ebene die Gebiete findet, ist klar. Aber wo sind die Gebiete von zum Beispiel dem K_3,3 oder dem K₅ , die ja bekanntermaßen nicht planar sind?

---

Guten Tag oswald

Das kann ich Ihnen leider nicht sagen. Benötigt man K_3,3 und K₅? Falls man dies benötigt, dann denke ich nicht das man diese Formel für dies einsetzen kann.

Vielen Dank im Voraus!

MfG
Lenovo

---

Zu jeder Fläche gibt es einen Kreis, der diese Fläche begrenzt.

Welche Kreise eines Graphen aber zu Flächen werden, hängt von der Einbettung ab:

   1
  / \
 /   \
2-----3
|\   /|
| \ / |
4--5--6

Diese Einbettung hat fünf Flächen, von denen vier durch 3 Kanten begrenzt sind und eine durch 6 Kanten begrenzt ist.

   1
  / \
 /   \
2-----3
|\   /|
| 4 / |
| |/  |
+-5---6

Diese Einbettung hat ebenfalls fünf Flächen, von denen drei durch 3 Kanten begrenzt sind, eine durch 4 Kanten und eine durch 5 Kanten. Es ist aber der selbe Graph wie oben.

Das kann ich Ihnen leider nicht sagen.

Man weiß zwar nicht, welche Flächen es gibt, aber wie viele es gibt und dass sie aus Kreisen bestehen. Man bestimmt also die Menge aller Kreise und probiert jede f-elementige Teilmenge davon aus. Etwas mühselig wird dann aber, das Argument "Ich habe keine Einbettung gefunden, also gibt es keine" zu begründen. Im wesentlichen wird durch Eulers Polyeder-Formel der Suchraum kleiner.

Benötigt man K_3,3 und K₅?

Das waren nur Beispiele. Für den Satz von Kuratowski benötigt man diese Graphen.

---

Weil jedes Gebiet durch mindestens 3 Kanten begrenzt wird und jede Kante genau zwei Gebiete voneinander trennt, gilt für planare Graphen

        2k ≥ 3f,

also

        f ≤ \(\frac{2}{3}\)k

Der K₅ hat 5 Ecken und 20 Kanten, also muss

        5 + f - 20 = 2

und somit

        f = 17

sein. Allerdings ist

        \(17 \nleq \frac{2}{3}\cdot 20\).