Mathematik Graphentheorie – Planare Graphen
Karteikarten zum Thema „Mathematik“ · 15 Karten · von atrio. Beispiele: Was ist ein planarer Graph? · Wie lautet die eulersche Polyederformel für zusammenhän…
Karten
15 KartenWas ist ein planarer Graph?
Rückseite
Ein Graph, der in der Ebene zeichnen lässt, ohne dass sich Kanten schneiden – außer in gemeinsamen Knoten.
Wie lautet die eulersche Polyederformel für zusammenhängende planare Graphen?
Rückseite
Für einen zusammenhängenden planaren Graphen mit n Knoten, m Kanten und f Flächen gilt: n - m + f = 2.
Welche obere Schranke für die Kantenanzahl ergibt sich aus der eulerschen Formel für planare Graphen mit n ≥ 3?
Rückseite
Ein planarer Graph mit n ≥ 3 Knoten hat höchstens m ≤ 3n - 6 Kanten.
Was besagt das Kuratowski-Theorem zur Charakterisierung planarer Graphen?
Rückseite
Ein Graph ist genau dann planar, wenn er keinen Untergraphen enthält, der eine Unterteilung von K5 oder K3,3 ist.
Warum sind K5 und K3,3 nicht planar?
Rückseite
K5 hat 5 Knoten und 10 Kanten (verletzt m ≤ 3n-6), K3,3 hat 6 Knoten, 9 Kanten und keinen Dreieckszug – beide erzwingen Kantenkreuzungen.
Was ist der Unterschied zwischen einem Teilgraphen und einer Unterteilung (Homöomorphie) in Kuratowskis Sinne?
Rückseite
Eine Unterteilung entsteht durch Einfügen von Knotengrad-2-Knoten auf Kanten; Teilgraphen lassen Kanten/Knoten weg. Kuratowski fordert Unterteilungen.
Was besagt das Wagner-Theorem als Alternative zu Kuratowski?
Rückseite
Ein Graph ist planar genau dann, wenn er weder K5 noch K3,3 als Minor enthält (Minor = durch Kantenkontraktion und -löschung erreichbar).
Wie ist das duale Graph zu einer planaren Einbettung definiert?
Rückseite
Knoten des Dualen entsprechen Flächen der Einbettung; zwei Dualknoten sind benachbart, falls die Flächen eine Kante teilen.
Was besagt der Vierfarbensatz für planare Graphen?
Rückseite
Die Knoten jedes planaren Graphen lassen sich mit vier Farben färben, sodass benachbarte Knoten unterschiedliche Farben erhalten.
Was ist eine Triangulation in der Graphentheorie?
Rückseite
Eine maximale planare Einbettung, bei der jede Fläche (einschließlich der äußeren) von genau drei Kanten begrenzt wird.
Wie viele Kanten hat eine Triangulation mit n ≥ 3 Knoten?
Rückseite
Genau 3n - 6 Kanten – die obere Schranke wird erreicht, alle Flächen sind Dreiecke.
Was sind äußerplanare Graphen?
Rückseite
Graphen, die planar einbettbar sind, sodass alle Knoten auf der äußeren Fläche liegen. Sie erfüllen m ≤ 2n - 3.
Welchen Algorithmus nutzt man zur linearen Planaritätsprüfung?
Rückseite
Der Hopcroft-Tarjan-Algorithmus prüft Planarität in O(n) Zeit mittels Tiefensuche und Pfadzerlegung.
Was ist der Unterschied zwischen einem planaren und einem ebenen Graphen?
Rückseite
Ein planarer Graph besitzt mindestens eine kreuzungsfreie Einbettung; ein ebener Graph ist ein planarer Graph mit einer fixierten, konkreten Einbettung.
Wie lässt sich die Planarität eines Graphen mit n=4, m=6 testen?
Rückseite
K4 hat n=4, m=6 und erfüllt m=6 ≤ 3·4-6=6 – die Schranke ist erfüllt, K4 ist planar (tetraedrische Einbettung).