Eulersche Polyederformel und Kantenbeschränkung

#Studium #Informatik #Definition #DS

Die Eulersche Polyederformel definiert eine starre, invariante mathematische Balance-Gleichung für jeden zusammenhängenden planaren Graphen in einer ebenen Einbettung.

Formale Definition: Für jeden zusammenhängenden planaren Graphen $G$ mit der Knotenmenge $V$ , der Kantenmenge $E$ und der Menge der Gebiete $F$ gilt zwingend: $| V | - | E | + | F | = 2 ⟺ | F | = | E | - | V | + 2$
Korollar zur Kantenbeschränkung: Aus der Polyederformel folgt durch Triangulierung der Gebiete, dass ein planarer Graph mit $| V | \geq 3$ strukturell niemals beliebig viele Kanten besitzen kann. Es gilt die harte obere Schranke: $| E | \leq 3 | V | - 6$
Minimalgrad-Schranke: Jeder planare Graph besitzt mindestens einen Knoten mit einem Grad von maximal $5$ ( $\exists v \in V : d (v) \leq 5$ ). Ein planarer Graph kann keinen Minimalgrad $δ (G) \geq 6$ aufweisen.