Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 25/latex
\setcounter{section}{25}
\zwischenueberschrift{Geometrische Realisierung eines Graphen}
Es sei
\mathl{(V,E)}{} ein
\definitionsverweis {Graph}{}{.}
Wir realisieren die Knotenmenge als Menge der Standardvektoren
\mathkor {} {e_v} {} {v \in V} {,}
im reellen Vektorraum $\R^V$, also der Menge aller $V$-Tupel mit Werten in $\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
\mathkor {} {u} {und} {v} {}
realisieren wir als die Strecke
\mathdisp {se_u + (1-s)e_v,\, s \in [0,1]} { . }
Diese Strecke enthält
\mathkor {} {e_u} {und} {e_v} {}
als Endpunkte, für
\mathkor {} {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
\zusatzklammer {überschneidungsfreie} {} {}
geometrische Realisierung des Graphen im Sinne der folgenden Definition vor.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{.}
Eine
\zusatzklammer {überschneidungsfreie} {} {}
\definitionswort {geometrische Realisierung}{}
von $G$ im $\R^d$ besteht aus folgenden Daten.
\aufzaehlungdrei{Eine
\definitionsverweis {injektive}{}{}
Abbildung
\maabbeledisp {} {V} { \R^d
} {v} {P_v
} {,}
zu jedem Knotenpunkt
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es also einen Punkt
\mavergleichskette
{\vergleichskette
{P_v
}
{ \in }{ \R^d
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und verschiedene Knotenpunkte besitzen verschiedene Realisierungen $P_v$.
}{Zu jeder Kante
\mavergleichskette
{\vergleichskette
{L
}
{ = }{ \{u ,v \}
}
{ \in }{E
}
{ }{
}
{ }{
}
}
{}{}{}
eine injektive
\definitionsverweis {stetige}{}{}
Abbildung
\maabbdisp {\varphi_L} {[0,1]} {\R^d
} {}
mit
\mavergleichskette
{\vergleichskette
{ \varphi_L(0)
}
{ = }{ P_u
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \varphi_L(1)
}
{ = }{ P_v
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Für verschiedene Kanten
\mavergleichskette
{\vergleichskette
{L
}
{ \neq }{L'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{ \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 \zusatzklammer {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 $\R^V$ heißt \stichwort {Standardrealisierung} {.} Sie ist hochdimensional, eine sinnvolle Fragestellung ist, in welcher niedrigeren Dimension man einen Graphen ebenfalls realisieren kann.
\zwischenueberschrift{Dreidimensionale Realisierungen}
Ein ungerichteter Graph
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
lässt sich stets dreidimensional realisieren, d.h. durch eine überschneidungsfreie geometrische Realisierung im $\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
\definitionsverweis {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 \zusatzklammer {ab dem dritten} {} {} Punkten durch \anfuehrung{Schnüre}{} \zusatzklammer {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.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {3page_K5.svg} }
\end{center}
\bildtext {} }
\bildlizenz { 3page_K5.svg } {} {David Eppstein} {Commons} {gemeinfrei} {}
Man platziert die Punkte auf einer Geraden und betrachtet im Raum hinreichend viele Halbebenen \zusatzklammer {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
\mathbed {P_i} {}
{i = 1 , \ldots , n} {}
{} {} {} {,}
in der Ebene
\mavergleichskettedisp
{\vergleichskette
{ \R^2 \times \{ 0 \}
}
{ \subseteq} { \R^3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{ \epsilon
}
{ > }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart, dass die $\epsilon$-Umgebungen der Punkte zueinander disjunkt sind. Sei
\mavergleichskette
{\vergleichskette
{m
}
{ = }{ \binom { n } { 2 }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Man platziert nun in der $\epsilon$-Umgebung von einem jeden Punkt $P_i$ jeweils $n$ Punkte $Q_{ij}$
\zusatzklammer {Liftungspunkte} {} {}
und setzt diese in die Ebene
\mavergleichskettedisp
{\vergleichskette
{ \R^2 \times \{m\}
}
{ \subseteq} { \R^3
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Der Punkt $P_i$ wird durch gerade
\zusatzklammer {ziemlich vertikale} {} {}
Strecken $V_{ij}$ mit seinen $n$ Liftungspunkten verbunden. Diese Verbindungsstrecken liegen allesamt im Schlauch
\mathl{U { \left( P_i,\epsilon \right) } \times [0,m]}{.} Zu jedem Punktepaar
\mavergleichskette
{\vergleichskette
{P_i
}
{ \neq }{P_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gehört eine Ebene $\R^2 \times {\ell}$,
\mavergleichskette
{\vergleichskette
{ \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 \anfuehrung{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 \zusatzklammer {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 \mathkor {} {v} {und} {w} {} \zusatzklammer {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 \definitionsverweis {geometrischen Realisierung}{}{} eines Graphen wie der \definitionsverweis {Standardrealisierung}{}{} kann man durch eine generische \zusatzklammer {orthogonale} {} {} \definitionsverweis {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.
\zwischenueberschrift{Eindimensionale Realisierungen}
Ein zusammenhängender Graph besitzt genau dann eine eindimensionale geometrische Realisierung, wenn es ein Pfad ist.
\zwischenueberschrift{Ebene Graphen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {3-simplex graph.svg} }
\end{center}
\bildtext {Eine ebene nicht überschneidungsfreie Skizze} }
\bildlizenz { 3-simplex graph.svg } {} {Koko90} {Commons} {CC-by-sa 3.0} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {3-demicube t0 B3.svg} }
\end{center}
\bildtext {und eine ebene überschneidungsfreie Realisierung des vollständigen Graphen mit vier Punkten.} }
\bildlizenz { 3-demicube t0 B3.svg } {} {Tomruen} {Commons} {gemeinfrei} {}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Cube skeleton.svg} }
\end{center}
\bildtext {Eine ebene Realisierung des Würfelgraphen} }
\bildlizenz { Cube skeleton.svg } {} {Apocheir} {Commons} {gemeinfrei} {}
\inputdefinition
{}
{
Ein \definitionsverweis {Graph}{}{} heißt \definitionswort {planar}{,} wenn er eine \definitionsverweis {geometrische Realisierung}{}{} im $\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.
\inputbemerkung
{}
{
An einem \zusatzklammer {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 \zusatzklammer {ohne Endpunkt} {} {} oder gehört zu genau einem Gebiet \zusatzklammer {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 \zusatzklammer {endliche} {} {} Gebiet grenzen zumindest drei Weg an.
Es gibt ein äußeres unendliches Gebiet.
}
\zwischenueberschrift{Die eulersche Polyederformel}
\inputfaktbeweis
{Planarer Graph/Eulersche Polyederformel/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $G$ ein
\definitionsverweis {zusammenhängender}{}{}
\definitionsverweis {planarer Graph}{}{}
mit $n$ Knotenpunkten, $m$ Kanten und $g$ Gebieten.}
\faktfolgerung {Dann gilt die \stichwort {eulersche Polyederformel} {}
\mavergleichskettedisp
{\vergleichskette
{n-m+g
}
{ =} {2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir führen Induktion über die Anzahl $g$ der Gebiete. Bei
\mavergleichskette
{\vergleichskette
{g
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
liegt ein
\definitionsverweis {Baum}{}{}
vor und nach
Satz 17.22
ist
\mavergleichskettedisp
{\vergleichskette
{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
\definitionsverweis {Zykel}{}{}
und damit auch einen
\definitionsverweis {Kreis}{}{,}
sagen wir
\mavergleichskette
{\vergleichskette
{v_1
}
{ \sim }{v_2
}
{ \sim \ldots \sim }{v_r
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei der Herausnahme der Kante
\mathl{v_1v_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
\mathl{v_1v_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$.
\inputfaktbeweis
{Planarer Graph/Eulersche Polyederformel/Gebietsanzahl/Fakt}
{Korollar}
{}
{
\faktsituation {Zu einem
\definitionsverweis {zusammenhängenden}{}{}
\definitionsverweis {planaren Graphen}{}{}}
\faktfolgerung {ist die Anzahl der Gebiete unabhängig von der ebenen Realisierung.}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt unmittelbar aus Satz 25.4.
\inputfaktbeweis
{Planarer Graph/Eulersche Polyederformel/Abschätzungen/Fakt}
{Korollar}
{}
{
\faktsituation {Für einen
\definitionsverweis {zusammenhängenden}{}{}
\definitionsverweis {planaren Graphen}{}{}
mit
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Knoten und $m$ Kanten}
\faktvoraussetzung {gelten die folgenden Gesetzmäßigkeiten.}
\faktfolgerung {\aufzaehlungzwei {Es ist
\mavergleichskettedisp
{\vergleichskette
{ m
}
{ \leq} { 3n-6
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
} {$G$ besitzt einen Knoten, dessen
\definitionsverweis {Grad}{}{}
höchstens $5$ ist.
}}
\faktzusatz {}
\faktzusatz {}
}
{
(1). Es sei $g$ die Anzahl der Gebiete. Zu jedem Gebiet $G$ sei
\mathl{E(G)}{} die Menge der das Gebiet begrenzenden Kanten. Da jede Kante an maximal zwei Gebieten beteiligt ist und da jedes Gebiet
\zusatzklammer {wegen der Voraussetzung, dass es zumindest drei Knoten und dann auch drei Kanten gibt} {} {}
zumindest drei begrenzende Kanten besitzt, gilt
\mavergleichskettedisp
{\vergleichskette
{ 2m
}
{ \geq} { \sum_{G \text{ Gebiet} } { \# \left( E(G) \right) }
}
{ \geq} {3g
}
{ } {
}
{ } {
}
}
{}{}{.}
Mit
der eulerschen Polyederformel
gilt daher
\mavergleichskettedisp
{\vergleichskette
{2m
}
{ \geq} { 3( 2-n+m)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und somit
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{2m
}
{ \geq }{ 6n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
was der Eigenschaft (1) widerspricht.
\inputbeispiel{}
{
Der
\definitionsverweis {vollständige Graph}{}{}
$K_5$ besitzt $5$ Knoten und
\mavergleichskette
{\vergleichskette
{ \binom { 5 } { 2 }
}
{ = }{ 10
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Kanten. Nach der Abschätzung aus
Korollar 25.6 (1)
kann er also nicht
\definitionsverweis {planar}{}{}
sein.
}
\inputbeispiel{}
{
Der \definitionsverweis {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 \definitionsverweis {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.
}