Planarer Graph - LinkFang.de





Planarer Graph


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.

Definition

Ein Graph [math] G=(V,E) [/math] heißt planar oder plättbar, wenn er eine Einbettung in die Ebene besitzt; das heißt, er kann in der Ebene gezeichnet werden, so dass seine Kanten durch Jordan-Kurven repräsentiert werden, welche sich nur in gemeinsamen Endpunkten schneiden. Die Einbettung (auch Zeichnung) des Graphen ist ein ebener Graph. Nach dem Satz von Wagner und Fáry existiert für jeden planaren Graphen auch eine Einbettung, in welcher seine Kanten als (gradlinige) Strecken dargestellt sind.

Durch die Einbettung wird die Ebene in zusammenhängende Gebiete (auch Flächen) geteilt, die von den Kanten des Graphen begrenzt werden. Die begrenzenden Kanten eines Gebietes bilden seinen Rand. Das unbeschränkte Gebiet um den Graphen herum wird äußeres Gebiet oder äußere Fläche genannt. Zwei Einbettungen heißen äquivalent, wenn es eine isomorphe Abbildung zwischen den Rändern ihrer Gebiete gibt.

Verwandte Begriffsbildungen

Ein Graph heißt maximal planar oder Dreiecksgraph, wenn er planar ist und ihm keine Kante hinzugefügt werden kann, ohne dass dadurch seine Planarität verloren geht.

Ein Graph heißt fast planar oder kritisch planar, wenn der Graph durch Entfernen eines beliebigen Knotens planar wird. Beispiel: K5 ist fast planar.

Ein Graph heißt außerplanar (oft auch außenplanar oder kreisartig planar), wenn er sich so in die Ebene einbetten lässt, dass alle seine Ecken auf dem Rand ein und desselben Gebiets liegen.

Eigenschaften

  • Der Satz von Kuratowski gibt eine nicht-geometrische Charakterisierung von planaren Graphen und erlaubt die Beantwortung der Frage nach der Plättbarkeit von Graphen.
  • Aus dem eulerschen Polyedersatz ergibt sich, dass die Gebietsanzahl jeder Einbettung dieselbe ist.
  • Für einen planaren Graphen ohne Schleifen und Mehrfachkanten ergibt sich aus dem Polyedersatz die Abschätzung [math] | E | \leq 3 | V | - 6[/math]. Dies lässt sich für dreiecksfreie Graphen mit mindestens 3 Knoten noch auf die folgende Ungleichung verbessern: [math] | E | \leq 2 | V | - 4 [/math]
  • Ist ein planarer Graph 3-fach zusammenhängend, so sind alle seine Einbettungen (bis auf eine globale Umorientierung) äquivalent.
  • Ein planarer Graph mit [math] n \geq 3 [/math] Knoten ist genau dann maximal planar, wenn er [math] 3n-6 [/math] Kanten hat.
  • Ein planarer Graph kann höchstens 5-fach zusammenhängend sein und es gibt immer einen Knoten mit Knotengrad höchstens 5.

Die Planarität eines Graphen lässt sich mit verschiedenen Algorithmen in linearer Zeit testen.

Verwendung

Die Untersuchung der Planarität von Graphen gehört zu den klassischen Themengebieten der Graphentheorie und wird auch oftmals als starke Voraussetzung für Sätze verwendet. So besagt der Vier-Farben-Satz, dass sich planare Graphen mit 4 Farben färben lassen. Dreiecksfreie planare Graphen sind 3-färbbar.

Literatur


Kategorien: Topologische Graphentheorie | Planarer Graph

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Planarer Graph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.