Dreiecksgraph
Der
Goldner–Harary
Graph ist maximal planar. Jedes Gebiet wird von drei Kanten
umrandet.
Ein Dreiecksgraph ist in der Graphentheorie
ein planarer
Graph, bei dem jedes seiner Gebiete durch einen Kreis der Länge
umrandet ist. Ein Dreiecksgraph hat daher mindestens drei Knoten.
Ein maximal planarer Graph (oder maximal ebener Graph) ist ein planarer Graph, dem keine Kante hinzugefügt werden kann, ohne dass dadurch seine Planarität verloren geht. Jeder Graph mit mindestens drei Knoten ist genau dann maximal planar, wenn er ein Dreiecksgraph ist.
Ein Dreiecksgraph mit 
Knoten
hat genau 
Kanten und 
Gebiete. Der kleinste Dreiecksgraph ist der Kreisgraph
bestehend aus genau drei Knoten.
Literatur
- Reinhard Diestel: Graphentheorie. Springer, 2006, ISBN 3-540-21391-0.
Wikipedia.de
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 07.03. 2021