date-created: 2024-04-22 02:55:53 date-modified: 2024-07-04 06:59:45

Darstellung von Graphen

anchored to 115.00_graphentheorie_anchor builds upon 115.01_grundlagen

Jordan-Kurven

Wir möchten ferner Jordankurven einführen, welche wir später zur Darstellung von Graphen benötigen werden.

[!Definition]

Eine offene Jordankurve ist eine homöomorphe (stetige Abbildung zwischen zwei topologischen Räumen) Einbettung des Intervalls $[0,1]$ in einem topologischen Raum! –> Kurz einfach solche die sich nicht schneiden und stetig sind. und ein Anfang/Ende haben

[!Tip] Jordan-Kurven visuell

Jordan-Kurven sind prinzipiell einfach solche Kurven, die in einem Bereich stetig und schnittpunktfrei sind, also sich selbst nicht schneiden ( außer sie sind geschlossen) und halt in einem Raum existieren.

Diese Definition werden wir bei der Betrachtung von planaren Graphen nochmals verwenden

Darstellung in ${\mathbb{R}}^2$ Ebenen

[!Definition] Darstellung in einer Ebene | Möglichkeiten (2) #card

Sei $G=(V,E)$ ein Graph. Wir können einen Graph auf einer Ebene $\in {\mathbb{R}}^2$ geometrisch realisieren/darstellen.

1. Knoten werden auf paarweise verschiedene Punkte abgebildet ( also Einordnung in die Ebene durch mögliche Translation)
2. Kanten werden einfach Kurven - Jordan-Kurven - zwischen den entsprechenden Knoten

Zeichnung eines Graphen

[!Definition] Zeichnung von $G=(V,E)$ #card

Sei $G=(V,E)$ ein Graph Wir bezeichnen jetzt eine Abbildung $\Gamma$ eine Zeichnung von $G$, falls folgende Eigenschaften erfüllt werden:

• $\forall v\in V:\Gamma (v)\in {\mathbb{R}}^2$ -> also ein jeder Knoten wird im zwei-dimensionalen Raum translatiert
• $\forall uv\in E:\Gamma (uv)={\Gamma }_{uv}([0,1])$ Wir übersetzen also eine Kante zwischen zwei Knoten zu einer Jordan-Kurve (daher der Intervall $[0,1]$)
• Hierbei ist dann ${\zeta }_{uv}$ eine Jordankurve mit ${\Gamma }_{uv}(0)=\Gamma (u)\wedge {\Gamma }_{uv}(1)=\Gamma (v)$
  • Also ferner ist der Start gleich der Koordinate von Knoten $u$ und das Ende gleich der Koordinate von $u$ im Zielraum

Kreuzungsfreie Zeichnungen

Als erweiterte Form einer Zeichnung $\Gamma$ können wir jetzt noch die Eigenschaft der kreuzungsfreien Zeichnung einführen. Hierbei muss folgend gelten: was? #card

$ab\ne cd\in E⟹{\Gamma }_{ab}([0,1])\cap {\Gamma }_{cd}(]0,1[]=\varnothing )$ Also die Zeichnungen dürfen sich bei verschiedenen Kanten maximal in den Endpunkten (0,1) schneiden, sonst nicht. –> Daher wird bei ${\Gamma }_{cd}$ der Interval anders definiert und schließt die beiden Werte aus.

Planarer Graph | plättbar

[!Definition] Wir möchten jetzt einen Graphen planar oder plättbar nennen, wenn er eine eben Zeichnung hat.

Was meinen wir mit ebener Zeichnung? #card

-> Also eine solche, wo die Jordankurven sich nicht schneiden.

$G\text{ ist planar }⟹G\text{ hat eine ebene Zeichnung}$

Teils wird hierbei auch gefordert, dass dann alle Kanten geradlining sein müssen. -> Diese Variante einer Zeichnung nennt man dann geradlinige Zeichnung (straight-line drawing)

Plättbar impliziert hier :: dass es möglich ist den Graphen in einem - mehreren - Schritt(en) so umzuformen, dass er die Eigenschaft erfüllt. Weiterhin könnte er so beispielsweise zu einer geradlinigen Zeichnung transformiert werden:

Betrachten wir jetzt einen solchen Graphen in seiner Ebenenenzeichnung, dann teilt es ihn in zusammenhängende Flächen / Gebiete ein, die wir als Facetten bezeichnen. Ferner sind nur bei Planaren Graphen Facettenaufteilungen möglich ( wenn sich der Graph in seiner Darstellung schneidet, dann haben diese Schnittteile keine Facetten!) Außenfacetten bezeichnen: DIe nicht vom Graphen eingeschlossene Facette Innenfacetten bezeichnen: Alle vom Graphen “eingeschlossenen” Facetten / Flächen.

Außenfacetten sind beliebig wählbar

[!Definition] beliebig wählbare Außenfacette Sei $G\text{ planar},\pi \text{ eine ebene Zeichnung von }G$ und $F$ die Innenfacetten von $\pi$.

Wie können wir diese Zeichnung noch darstellen? #card

Dann können wir jetzt auch eine ebene Zeichnung ${\pi }_F$ von $G$ finden, in der $E(F_0)$ dn Rand der Außenfacette bildet.

Beweis | Außenfacetten sind beliebige wählbar

Betrachten wir die Umkehrung der stereografischen Projektion $\sigma :S^2\setminus \{N\}\to {\mathbb{R}}^2$, also ${\sigma }^{-1}$, die eine eben Zeichnung von $G$ auf der Kugeloberfläche zeichnet:

Wir können durch eine beliebige Rotation dieser Kugel, also $\delta :{\mathbb{R}}^3\to {\mathbb{R}}^3$ die Kugel so rotieren, dass anschließend $N\in Inn({\sigma }^{-1}(F))$ ist ( also wir die Rotation entsprechend anpassen konnten.) Anschließend können wir diese Struktur wieder auf die Ebene zurückprojizieren –> also von Punkt $N$ entsprechend Geraden durch die Ecken der Facette ziehen und auf die Ebene projizieren (wir haben sie ja rotiert).

Anschließend folgt jetzt: $⟹$ die Zeichnung von $E(F)$ begrenzt jetzt die Außenfacette - ist also quasi die gleiche Grundstruktur, aber durch eine andere Betrachtung jetzt “anders aufgebaut”. Ferner gilt jetzt: $${\pi }_F=\sigma \circ \delta \circ {\sigma }^{-1}\circ \pi =\text{ ist eben}$$

Anders formuliert: Wir möchten den blauen Teil als Außenfacette wählen: Wir projizieren, diese Facette auf eine Einheitskugel $K$ und haben “dahinter” einen Punkt $N$ auf welchen wir projizieren. Hierbei ist es dann so, dass durch die Projektion die Kugel geschnitten wird und wir hierbei dann eine Fläche auf der Kugel erhalten. Dann kann man diese Kugel (mit der Projektion drauf) drehen und anschließend wieder von $N$ auf den Boden projizieren: Dadurch ist jetzt die Facette eine Außenfacette.

Skelette sind planar:

[!Attention] Polyeder macht man in der Schule! Haben wir während der Vorlesung evaluiert!

[!Definition] Skellet eines bestimmten Polyeders

Betrachten wir ein konvexes / beschränktes Polyeder. Wir können jetzt festhalten, dass das SKelett ( Ecken-Adjazengraph/Gerüstgraph des Körpers) eines konvexen und beschränkten Polyeders planar ist.

Hat zweidimensionale Flächen, die

Den Beweis dieser Aussage können wir folgend konstruieren: Sei $P$ das besagte konvexe, beschränkte Polyeder, $o\in Inn(P)$ Sei ferner $S$ die Kugel mit dem Zentrum $o$, so dass gilt $P\subset S$ (Wir umschließen also das Polyeder mit der Kugel und können somit anschließend die Projektion aus Außenfacetten sind beliebige wählbar anwenden ) Diese Kugel kann beliebig groß sein! Wir wenden nun die Zentralprojektion ${\pi }_0:P\to S$ an, welche die ebene Zeichnung ${\pi }_S$ des Skeletts von $P$ auf der Kugeloberfläche on $S$ erzeugt. Jetzt können wir nach selbigen Prinzip wie zuvor den Nordpol $N$ bestimmen, wobei $N\notin {\pi }_S$ Anschießend wollen wir ${\pi }_s$ mittels $\sigma$ auf die Ebene projizieren. Die Verbindung: $\sigma \circ {\pi }_S$ ist nun eben und somit eine entsprechende Aufstellung als planarer Graph

triangulierter Donut als Gegenbeispiel, dass es bei nicht-konvexen Polyedern nicht möglich ist. Das wird auch sehr schwer, wenn man etwa Polyeder betrachtet, die in sich “Gänge” aufweisen, den die kann man schlecht / nicht projezieren.

Maximal Planare Graphen

[!Satz]

Ein Graph $G$ heißt maximal planar, wenn $G$ einfach ist und man keine weitere Kante einfügen kann, ohne die Planarität zu zerstören!

welche Folgerung können wir hieraus ziehen? Unter Betrachtung der Grafik, ist er bereits planar? #card

Es folgt hieraus, dass alle Flächen von genau drei Kanten begrenzt werden –> Was man dann auch als Triangulierung bezeichnet.

[!Attention] Bezug zur 4-Farbenvermutung:

Zum Beweis der 4-Farbenvermutung genügt es zu zeigen, dass alle maximal planaren Graphen $4-$färbbar sind.

In unserem Beispiel kann man noch folgend erweitern:

Satz (52) | Folgerungen für maximal planare Graphen

[!Tip] Satz (52) | Folgerungen für maximal planaren Graph:

Betrachten wir einen Graphen $G=(V,E)$, welcher ein maximal planarer Graph mit $n=|V|\ge 4$ und $m=|E\mid$ ist.

Es gelten jetzt 6 Aussagen:

1. Alle Flächen sind Dreiecke

–> Das folgt unmittelbar aus der Definition bzw. aus 115.83_uebung03 Aufgabe 2

2. Es gilt: $d(v)\ge 3,\forall v\in V$

Wie wird das bewiesen / gezeigt?

3. $m=3n-6$

Wie können wir die einzelnen Aussagen beweisen?! #card

Für:

2. Wir können sagen, dass jeder Knoten inzident zu $>3\Delta$ ist. Man kann es auch durch einen Widerspruch beweisen: Angenommen es gibt $v$ mit $deg(v)=2$, dann kann man noch eine Kante von $v$ zu einem anderen Knoten einfügen - hierbei ist $v$ zur Fläche inzident, die noch kein Dreieck ist! (Somit bilden / schließen wir es und haben entsprechend eine weitere Kante bilden können)

3. Lösunge siehe 115.83_uebung03 Aufgabe 2

4. Wir könnten über 3 zeigen oder über die eulersche Formel:

$\sum _v(deg(v))=2m$ und wir wissen aus 3: $$\begin{array}{r}>m=3n-6⟺2m=6n-12⟺\sum _v(deg(v))=6n-12\\ >12=6n-\sum _v(deg(v))⟺12=\sum _v(6-deg(v))>\end{array}$$

6. G ist 3-zusammenhängend

Diese Aussage folgt direkt aus $5$, da wir einen Kreis gefunden haben, der $\ge 3$ Knoten aufweist

[!Req] Aussagen über maximal planare Graphen

Betrachten wir einen Graph $G=(V,E)$, welcher maximal planar mit $n=|V\mid \ge 4$ und $m=|E\mid$ ist.

Es gilt jetzt: 5.ist $T$ eine minimal trennende Knotenmenge, so ist der von $T$ aufspannende Untergraph ein kreis

Wie können wir das beweisen? #card

Zunächst intuitiv als visuelle Betrachtung:

Sei $T$ eine trennende Knotenmenge. Zeige, der von $T$ aufgespannt Untergraph $G(T)$ enthält einen Kreis.

Seien darin jetzt $v_1,v_2$ Knoten in unterschiedlichen Komponenten bei der Trennung durch $G\setminus T$.

Wenn $G(T)$ keinen Kreis enthält, gibt es eine Jordan Kurve $C$ von $v_1\to v_2$ die weder Knoten noch Kanten von $G(T)$ enthält.

Aber $G$ ist eine Triangulierung, das heißt, $C$ kann zu Kanten in $G\setminus T$ verbunden werden.

$v_1,v_2$ sind aber in unterschiedlichen Komponenten –> $G\setminus T$

Dualität

Betrachten wir einen Graphen $G=(V,E)$, welcher planar mit fester Einbettung ist. Ferner bezeichnet die Menge $F$ die Flächen des Graphes (Facetten).

[!Definition] Dualgraph Betrachten wir einen planaren Graphen mit fester Einbettung und $F$ als Flächen. Wir nennen jetzt folgende Konstruktion einen Dualgraph:

Was muss gelten, bzw. wie ist ein Dualgraph definiert? Was gilt für jede Kante? #card

$$G^{\ast =}(V^{\ast ,}{E}^{\ast ),}{V}^{\ast }=F$$

Zu jeder Kante $e\in E$ gibt es nun $e^{\ast }\in E^{\ast }$, was zwei Knoten $V^{\ast }$ verbindet, wenn die entsprechenden Flächen durch eine Kante $e$ getrennt sind.

Also:

• alle Knoten des Dualgraph beschreiben die Facetten eines Graphen $G$
• Jede Verbindung von Flächen $f$ ist als eine Kante zwischen den entsprechenden Knoten von $G^{\ast }$ zu verstehen und somit werden damit die Verbindungen dargestellt. (Wir haben quasi eine invertierte Isomorphie?)

Man kann hierbei sehen, dass Dualgraphen nicht immer einfache Graphen sind und somit vielleicht Zykel im Dualgraphen auftreten können (o.ä.)

Wir können diese Idee jetzt an das 4-Farben Problem knüpfen:

4-Farben Problem

Eine Färbung der Facetten - Länder - eines ebenen Graphen $G$ entspricht einer Knotenfärbung seines dualen Graphen.

Wir sehen hier, dass die Aufteilung und Bezeichnung äquivalent zu dem Problem ist.

Satz (19) | 4-Farben Vermutung == alle planaren Graphen sind 4-färbbar

[!Definition] Problemäquivalenz #card Die 4-Farben Vermutung 115.00_graphentheorie_anchor ist äquivalent zu der Vermutung, dass alle planaren Graphen 4-Färbbar sind!