Dreiecksgraph

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 3 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 Graphen mit mindestens drei Knoten ist genau dann maximal planar, wenn er ein Dreiecksgraph ist.

Ein Dreiecksgraph mit n Knoten hat genau 3n − 6 Kanten und 2n − 4 Gebiete.

Literatur


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Maximal planarer Graph — Ein Dreiecksgraph ist in der Graphentheorie ein Graph, der planar ist und dem keine Kante hinzugefügt werden kann, ohne dass dadurch seine Planarität verloren geht. Eine andere Bezeichnung für diese Eigenschaft ist maximal planar. Jedes Gebiet… …   Deutsch Wikipedia

  • Ebener Graph — Planare Zeichnung des K4 Ein planarer Graph (auch plättbarer Graph) ist in der Graphentheorie ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, so dass sich die Kanten nicht schneiden.… …   Deutsch Wikipedia

  • Plättbar — Planare Zeichnung des K4 Ein planarer Graph (auch plättbarer Graph) ist in der Graphentheorie ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, so dass sich die Kanten nicht schneiden.… …   Deutsch Wikipedia

  • Plättbarer Graph — Planare Zeichnung des K4 Ein planarer Graph (auch plättbarer Graph) ist in der Graphentheorie ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, so dass sich die Kanten nicht schneiden.… …   Deutsch Wikipedia

  • Triangulation (Punktemenge) — Eine Triangulation einer Menge von Punkten P in der Ebene bezeichnet eine Zerlegung der konvexen Hülle der Punktmenge in Dreiecke, wobei die Eckpunkte der Dreiecke genau die Punkte aus P sind. Somit ist die Triangulation ein ebener Dreiecksgraph …   Deutsch Wikipedia

  • Chordal — triangulierter Graph allgemeiner: perfekter Graph Schnittgraph Beispiele: Intervallgraphen Bäume Dreiecksgraphen In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er ei …   Deutsch Wikipedia

  • Chordale Graphen — triangulierter Graph allgemeiner: perfekter Graph Schnittgraph Beispiele: Intervallgraphen Bäume Dreiecksgraphen In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er ei …   Deutsch Wikipedia

  • Chordaler Graph — triangulierter Graph allgemeiner: perfekter Graph Schnittgraph Beispiele: Intervallgraphen Bäume Dreiecksgraphen In der Graphentheorie nennt man einen Graphen G trianguliert oder chordal, wenn er ei …   Deutsch Wikipedia

  • Gitter (Geometrie) — Ein Gitter in der Geometrie ist eine lückenlose und überlappungsfreie Partition eines Bereichs des Raumes durch eine Menge von Gitterzellen. Die Gitterzellen werden definiert durch eine Menge von Gitterpunkten, die untereinander durch eine Menge… …   Deutsch Wikipedia

  • Planarer Graph — Planare Zeichnung des K4 Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, sodass sich keine Kanten schneiden. Der Satz von… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”