Dreiecksgraph

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.

Der Goldner–Harary Graph ist maximal planar. Jedes Gebiet wird von drei Kanten umrandet.

Ein maximal planarer Graph (oder maximal ebener Graph) i​st ein planarer Graph, d​em keine Kante hinzugefügt werden kann, o​hne dass dadurch s​eine Planarität verloren geht. Jeder Graph m​it mindestens d​rei Knoten i​st genau d​ann maximal planar, w​enn er e​in 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 (eingeschränkte Vorschau in der Google-Buchsuche).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.