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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Geometrische Realisierung eines Graphen

Es sei ein Graph. Wir realisieren die Knotenmenge als Menge der Standardvektoren , im reellen Vektorraum , also der Menge aller -Tupel mit Werten in . Der Vektor hat also an der Stelle den Wert und an den anderen Stellen den Wert . Eine Kante zwischen zwei Knotenpunkten und realisieren wir als die Strecke

Diese Strecke enthält und als Endpunkte, für bzw. . Diese beiden Endpunkte sind zugleich die einzigen Punkte dieser Strecke, bei denen nur eine Koordinate von verschieden ist, bei den anderen Punkten der Strecke sind zwei Koordinaten von verschieden, nämlich die - und die -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  

Es sei ein Graph. Eine (überschneidungsfreie) geometrische Realisierung von im besteht aus folgenden Daten.

  1. Eine injektive Abbildung

    zu jedem Knotenpunkt gibt es also einen Punkt und verschiedene Knotenpunkte besitzen verschiedene Realisierungen .

  2. Zu jeder Kante eine injektive stetige Abbildung

    mit und .

  3. Für verschiedene Kanten ist

Zu einer jeden Kante in 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 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 lässt sich stets dreidimensional realisieren, d.h. durch eine überschneidungsfreie geometrische Realisierung im . 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 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.


3page K5.svg

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 Punkte , , in der Ebene

Es sei derart, dass die -Umgebungen der Punkte zueinander disjunkt sind. Sei . Man platziert nun in der -Umgebung von einem jeden Punkt jeweils Punkte (Liftungspunkte) und setzt diese in die Ebene

Der Punkt wird durch gerade (ziemlich vertikale) Strecken mit seinen Liftungspunkten verbunden. Diese Verbindungsstrecken liegen allesamt im Schlauch . Zu jedem Punktepaar gehört eine Ebene , . Die Punkte und werden nun dadurch miteinander verbunden, dass man von aus entlang und von aus entlang jeweils bis zum Durchstoßungspunkt mit der -Ebene hochgeht. Die beiden Durchstoßungspunkte werden dann horizontal in der -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 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 . Es seien also 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 und die Verbindungsstrecke zu zwei alten Punkten und (wichtig ist nur der Fall, wo diese Punkte verschieden sind) liegt in der durch definierten Ebene 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 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  

Ein Graph heißt planar, wenn er eine geometrische Realisierung im 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  

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  

Es sei ein zusammenhängender planarer Graph mit Knotenpunkten, Kanten und Gebieten.

Dann gilt die eulersche Polyederformel

Beweis  

Wir führen Induktion über die Anzahl der Gebiete. Bei liegt ein Baum vor und nach Satz 17.22 ist

Sei die Aussage nun für einen jeden planaren Graphen mit Gebieten bewiesen und sei ein zusammenhängender planarer Graph mit Gebieten. Es ist dann kein Baum und besitzt daher einen Zykel und damit auch einen Kreis, sagen wir . Bei der Herausnahme der Kante bleibt der Graph zusammenhängend und planar. Die Anzahl der Knoten bleibt gleich, die Anzahl der Kanten reduziert sich um und die beiden durch die Kante begrenzten Gebiete werden zu einem Gebiet vereinigt, die anderen Gebiete ändern sich nicht. Insgesamt reduziert sich also die Anzahl der Gebiete um . 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 , deshalb ist die Wechselsumme von ebenfalls gleich .




Korollar  

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.




Korollar  

Für einen zusammenhängenden planaren Graphen mit Knoten und Kanten gelten die folgenden Gesetzmäßigkeiten.

  1. Es ist
  2. besitzt einen Knoten, dessen Grad höchstens ist.

Beweis  

(1). Es sei die Anzahl der Gebiete. Zu jedem Gebiet sei 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

Mit der eulerschen Polyederformel gilt daher

und somit

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



Beispiel  

Der vollständige Graph besitzt Knoten und Kanten. Nach der Abschätzung aus Korollar 25.6  (1) kann er also nicht planar sein.



Beispiel  

Der vollständige bipartite Graph ist nicht planar. Er besitzt Knotenpunkte und Kanten. Wenn er planar wäre, so müsste es nach der eulerschen Polyederformel 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 Kanten an. Da jede Kante nur an Gebieten beteiligt ist, braucht man zumindest Kanten, ein Widerspruch.



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)