Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 25/kontrolle

Geometrische Realisierung eines Graphen

Es sei ${}(V,E)$ ein Graph. Wir realisieren die Knotenmenge als Menge der Standardvektoren ${}e_{v}$ ${}v\in V$, im reellen Vektorraum ${}\mathbb {R} ^{V}$, also der Menge aller ${}V$-Tupel mit Werten in ${}\mathbb {R}$. Der Vektor ${}e_{v}$ hat also an der Stelle ${}v$ den Wert ${}1$ und an den anderen Stellen den Wert ${}0$. Eine Kante zwischen zwei Knotenpunkten ${}u$ und ${}v$ realisieren wir als die Strecke

$se_{u}+(1-s)e_{v},\,s\in [0,1].$

Diese Strecke enthält ${}e_{u}$ und ${}e_{v}$ als Endpunkte, für ${}s=0$ bzw. ${}s=1$. Diese beiden Endpunkte sind zugleich die einzigen Punkte dieser Strecke, bei denen nur eine Koordinate von ${}0$ verschieden ist, bei den anderen Punkten der Strecke sind zwei Koordinaten von ${}0$ verschieden, nämlich die ${}u$- und die ${}v$-Koordinate. Die Strecken zu verschiedenen Kanten haben allenfalls einen Endpunkt gemeinsam, und dies ist genau dann der Fall, wenn die zugrunde liegenden Kanten im Graphen einen gemeinsamen Knotenpunkt besitzen. D.h. es liegt insbesondere eine (überschneidungsfreie) geometrische Realisierung des Graphen im Sinne der folgenden Definition vor.

Definition Referenznummer erstellen

Es sei ${}G=(V,E)$ ein Graph. Eine (überschneidungsfreie) geometrische Realisierung von ${}G$ im ${}\mathbb {R} ^{d}$ besteht aus folgenden Daten.

1. Eine injektive Abbildung

   $V\longrightarrow \mathbb {R} ^{d},\,v\longmapsto P_{v},$

   zu jedem Knotenpunkt ${}v\in V$ gibt es also einen Punkt ${}P_{v}\in \mathbb {R} ^{d}$ und verschiedene Knotenpunkte besitzen verschiedene Realisierungen ${}P_{v}$.

2. Zu jeder Kante ${}L=\{u,v\}\in E$ eine injektive stetige Abbildung

   $\varphi _{L}\colon [0,1]\longrightarrow \mathbb {R} ^{d}$

   mit ${}\varphi _{L}(0)=P_{u}$ und ${}\varphi _{L}(1)=P_{v}$.

3. Für verschiedene Kanten ${}L\neq L'$ ist

   ${}\varphi _{L}(]0,1[)\cap \varphi _{L'}(]0,1[)=\emptyset \,.$

Zu einer jeden Kante in ${}G$ gibt es also einen injektiven stetigen Verbindungsweg zwischen den zugehörigen geometrischen Punkten. Man bezeichnet diese stetigen Abbildungen als stetige Wege, manchmal auch die Bilder davon. Diese (Bilder der) Wege sind untereinander überschneidungsfrei in dem Sinne, dass allenfalls die geometrischen Endpunkte identisch sind. Letzteres liegt genau dann vor, wenn die beiden zugrunde liegenden Kanten einen gemeinsamen Endpunkt besitzen. Die oben beschriebene geometrische Realisierung des Graphen im ${}\mathbb {R} ^{V}$ heißt Standardrealisierung. Sie ist hochdimensional, eine sinnvolle Fragestellung ist, in welcher niedrigeren Dimension man einen Graphen ebenfalls realisieren kann.

Dreidimensionale Realisierungen

Ein ungerichteter Graph ${}G=(V,E)$ lässt sich stets dreidimensional realisieren, d.h. durch eine überschneidungsfreie geometrische Realisierung im ${}\mathbb {R} ^{3}$. Dafür gibt es mehrere Möglichkeiten, wobei wir hier die Ideen beschreiben und auf eine detaillierte Begründung verzichten. Da jeder Graph ein Untergraph eines vollständigen Graphen ist, und eine geometrische Realisierung eines Graphen direkt durch Weglassen von stetigen Wegen eine geometrische Realisierung eines Untergraphen ergibt, muss man lediglich begründen, dass man die vollständigen Graphen dreidimensional realisieren kann.

Man legt die ${}n$ Punkte auf eine Kreissphäre in der Ebene. Dann verbindet man den ersten Punkt mit den anderen Punkten durch gerade Strecken. Den zweiten Punkt verbindet man mit den weiteren (ab dem dritten) Punkten durch „Schnüre“ (mit einer gewissen Dicke), die über den schon liegenden Strecken verlaufen und ansonsten gestreckt sind. Den dritten Punkt verbindet man mit den weiteren Punkt durch Schnüre, die über den schon verwendeten Schnüren liegen, u.s.w. Die stetigen Wege kann man dann in der Querschnittsmitte der Schnüre realisieren.

Man platziert die Punkte auf einer Geraden und betrachtet im Raum hinreichend viele Halbebenen (Seiten eines Buches), die an dieser Geraden anliegen. Jetzt kann für jedes Punktepaar, das man verbinden möchte, einen Verbindungsbogen in einer dafür gewählten Halbebene zeichnen.

Man platziert die ${}n$ Punkte ${}P_{i}$, ${}i=1,\ldots ,n$, in der Ebene

${}\mathbb {R} ^{2}\times \{0\}\subseteq \mathbb {R} ^{3}\,.$

Es sei ${}\epsilon >0$ derart, dass die ${}\epsilon$-Umgebungen der Punkte zueinander disjunkt sind. Sei ${}m={\binom {n}{2}}$. Man platziert nun in der ${}\epsilon$-Umgebung von einem jeden Punkt ${}P_{i}$ jeweils ${}n$ Punkte ${}Q_{ij}$ (Liftungspunkte) und setzt diese in die Ebene

${}\mathbb {R} ^{2}\times \{m\}\subseteq \mathbb {R} ^{3}\,.$

Der Punkt ${}P_{i}$ wird durch gerade (ziemlich vertikale) Strecken ${}V_{ij}$ mit seinen ${}n$ Liftungspunkten verbunden. Diese Verbindungsstrecken liegen allesamt im Schlauch ${}U{\left(P_{i},\epsilon \right)}\times [0,m]$. Zu jedem Punktepaar ${}P_{i}\neq P_{j}$ gehört eine Ebene ${}\mathbb {R} ^{2}\times {\ell }$, ${}\ell =1,\ldots ,m$. Die Punkte ${}P_{i}$ und ${}P_{j}$ werden nun dadurch miteinander verbunden, dass man von ${}P_{i}$ aus entlang ${}V_{ij}$ und von ${}P_{j}$ aus entlang ${}V_{ji}$ jeweils bis zum Durchstoßungspunkt mit der ${}\ell$-Ebene hochgeht. Die beiden Durchstoßungspunkte werden dann horizontal in der ${}\ell$-Ebene durch eine gerade Strecke verbunden. In dieser Konstruktion werden alle Punkte miteinander überschneidungsfrei verbunden, da die Verbindungswege nur in den Schläuchen und in den verschiedenen Ebenen verlaufen.

Man ordnet die ${}n$ Knotenpunkte auf einer Kugeloberfläche an und verbindet je zwei Punkte durch „Fäden“. Dabei dürfen die Fäden im Allgemeinen nicht völlig straff sein. Wenn man die Punkte durch gerade Strecken verbinden möchte, so kann es bei einer gegebenen Punktkonfiguration auf der Kugeloberfläche zu Überschneidungen kommen. Diese kann man jedoch auch dadurch wegkriegen, dass man die einzelnen Punkte auf der Kugeloberfläche etwas bewegt. Dass dies möglich ist, beweist man durch Induktion über die Anzahl ${}n$. Es seien also ${}n$ Punkte auf der Kugeloberfläche gegeben mit der Eigenschaft, dass die Streckenverbindungen zu je zwei Punkten sich nicht treffen (außer in den Punkten selbst), und es soll noch ein weiterer Punkt hinzugenommen werden derart, dass auch die neuen Verbindungsstrecken dieses neuen Punktes mit den zuvor gegebenen Punkten keine Überschneidungen mit den alten Verbindungsstrecken besitzt. Ein alter Punkt ${}u$ und die Verbindungsstrecke zu zwei alten Punkten ${}v$ und ${}w$ (wichtig ist nur der Fall, wo diese Punkte verschieden sind) liegt in der durch ${}u,v,w$ definierten Ebene ${}F$ im Raum. Diese Ebene schneidet die Kugeloberfläche in einer Kreissphäre, und auf dieser darf der neue Punkt nicht liegen. Da es nur endlich viele Dreierpaare gibt, gibt es nur endlich viele Ebenen bzw. Sphären, die man ausschließen muss.

Aus einer hochdimensionalen geometrischen Realisierung eines Graphen wie der Standardrealisierung kann man durch eine generische (orthogonale) Projektion auf einen niedrigerdimensionalen Unterraum der Dimension ${}\geq 3$ eine weitere geometrische Realisierung erhalten. Die Projektionsrichtung muss dabei so gewählt sein, dass zwei Punkte nicht identifiziert werden und dass keine Überkreuzungen entstehen.

Eindimensionale Realisierungen

Ein zusammenhängender Graph besitzt genau dann eine eindimensionale geometrische Realisierung, wenn es ein Pfad ist.

Ebene Graphen

Eine ebene nicht überschneidungsfreie Skizze

und eine ebene überschneidungsfreie Realisierung des vollständigen Graphen mit vier Punkten.

Eine ebene Realisierung des Würfelgraphen

Definition Referenznummer erstellen

Ein Graph heißt planar, wenn er eine geometrische Realisierung im ${}\mathbb {R} ^{2}$ besitzt.

Unter einem Gebiet in der Ebene verstehen wir ein durch die Bilder von stetigen Wegen berandetes zusammenhängendes Flächenstück. Ein planar Graph bewirkt eine Einteilung der Ebene in Gebiete. Eine exakte Definition von Gebiet, Begrenzung, innen und außen gehört zur Topologie, wir fassen die für uns relevanten und intuitiv klaren Prinzipien kurz zusammen.

Bemerkung   Referenznummer erstellen

An einem (zu einer Kante des Graphen gehörenden) Weg liegen ein oder zwei Gebiete an.

Verschiedene Gebiete schneiden sich in einer Vereinigung von Wegen.

Jeder Punkt der Ebene ist entweder ein Bildpunkt eines Knotenpunktes oder gehört zu genau einem Weg (ohne Endpunkt) oder gehört zu genau einem Gebiet (ohne den Rand).

Zu einem Kreis des Graphen gehört ein geschlossener Weg, der die Ebene in ein Innen und Außen einteilt. Das Innere und das Äußere davon ist eine Vereinigung von Gebieten. Ein stetiger Weg von einem Punkt des Innern zu einem Punkt des Äußeren trifft den Begrenzungsweg.

An jedes geschlossene (endliche) Gebiet grenzen zumindest drei Weg an.

Es gibt ein äußeres unendliches Gebiet.

Die eulersche Polyederformel

Satz Satz 25.4 ändern

Es sei ${}G$ ein zusammenhängender planarer Graph mit ${}n$ Knotenpunkten, ${}m$ Kanten und ${}g$ Gebieten.

Dann gilt die eulersche Polyederformel

${}n-m+g=2\,.$

Beweis

Wir führen Induktion über die Anzahl ${}g$ der Gebiete. Bei ${}g=1$ liegt ein Baum vor und nach Satz 17.22 ist

${}n-m+1=n-(n-1)+1=2\,.$

Es sei die Aussage nun für einen jeden planaren Graphen mit ${}g$ Gebieten bewiesen und sei ${}G$ ein zusammenhängender planarer Graph mit ${}g+1$ Gebieten. Es ist dann ${}G$ kein Baum und besitzt daher einen Zykel und damit auch einen Kreis, sagen wir ${}v_{1}\sim v_{2}\sim \ldots \sim v_{r}$. Bei der Herausnahme der Kante ${}v_{1}v_{2}$ bleibt der Graph zusammenhängend und planar. Die Anzahl der Knoten bleibt gleich, die Anzahl der Kanten reduziert sich um ${}1$ und die beiden durch die Kante ${}v_{1}v_{2}$ begrenzten Gebiete werden zu einem Gebiet vereinigt, die anderen Gebiete ändern sich nicht. Insgesamt reduziert sich also die Anzahl der Gebiete um ${}1$. Da die Anzahl der Kanten und der Gebiete mit unterschiedlichem Vorzeichen in die Wechselsumme eingeht, ändert sich diese bei Herausnahme der Kante nicht. Nach Induktionsvoraussetzung ist die Wechselsumme des reduzierten Graphen gleich ${}2$, deshalb ist die Wechselsumme von ${}G$ ebenfalls gleich ${}2$.

$\Box$

Korollar Referenznummer erstellen

Zu einem zusammenhängenden planaren Graphen

ist die Anzahl der Gebiete unabhängig von der ebenen Realisierung.

Beweis

Dies folgt unmittelbar aus Satz 25.4.

$\Box$

Korollar Korollar 25.6 ändern

Für einen zusammenhängenden planaren Graphen mit ${}n\geq 3$ Knoten und ${}m$ Kanten gelten die folgenden Gesetzmäßigkeiten.

1. Es ist

   ${}m\leq 3n-6\,$

2. ${}G$ besitzt einen Knoten, dessen Grad höchstens ${}5$ ist.

Beweis

(1). Es sei ${}g$ die Anzahl der Gebiete. Zu jedem Gebiet ${}G$ sei ${}E(G)$ die Menge der das Gebiet begrenzenden Kanten. Da jede Kante an maximal zwei Gebieten beteiligt ist und da jedes Gebiet (wegen der Voraussetzung, dass es zumindest drei Knoten und dann auch drei Kanten gibt) zumindest drei begrenzende Kanten besitzt, gilt

${}2m\geq \sum _{G{\text{ Gebiet}}}{\#\left(E(G)\right)}\geq 3g\,.$

Mit der eulerschen Polyederformel gilt daher

${}2m\geq 3(2-n+m)\,$

und somit

${}m\leq 3n-6\,.$

(2). Nehmen wir an, dass sämtliche Knoten einen Grad ${}\geq 6$ haben. Dann ist die Summe über alle Knotengrade zumindest ${}6n$. Nach Lemma 15.16 ist daher ${}2m\geq 6n$, was der Eigenschaft (1) widerspricht.

$\Box$

Beispiel Beispiel 25.7 ändern

Der vollständige Graph ${}K_{5}$ besitzt ${}5$ Knoten und ${}{\binom {5}{2}}=10$ Kanten. Nach der Abschätzung aus Korollar 25.6  (1) kann er also nicht planar sein.

Beispiel Referenznummer erstellen

Der vollständige bipartite Graph ${}K_{3,3}$ ist nicht planar. Er besitzt ${}6$ Knotenpunkte und ${}9$ Kanten. Wenn er planar wäre, so müsste es nach der eulerschen Polyederformel ${}5$ Gebiete geben. Jedes dieser Gebiete wird durch einen Kreis berandet, und diese haben nach Satz 20.8 eine gerade Länge. Deshalb liegen an jedes Gebiet zumindest ${}4$ Kanten an. Da jede Kante nur an ${}2$ Gebieten beteiligt ist, braucht man zumindest ${}10$ Kanten, ein Widerspruch.