Westfälische Wilhelms-Universität Münster

Fachbereich 10 Mathematik und Informatik

Seminar „Graphentheorie“

Sommersemester 2015

Dozent: Dr. Thomas Timmermann

Grundlagen der Graphentheorie

17.04.2015

Jens Natrup

j_natr01@uni-muenster.de

2-Fach Bachelor

Mathematik und Sportwissenschaft

Fachsemester 6

Inhaltsverzeichnis

Seite

1. Einführung……………………………………...………… 1

2. Gerichtete Graphen……………………………..………… 1

3. Ungerichtete Graphen………..…………………………… 4

4. Isomorphie von Graphen……….………………………… 5

5. Untergraphen………….………………………………….. 6

6. Wege, Kreise und Zusammenhang……..………………… 7

7. Planare Graphen………..………………………………… 8

8. Färben von Graphen……………………………………… 9

9. Quellen- und Literaturverzeichnis……………….……….. 10

- 1 -

1. Einführung

In dieser Ausarbeitung werden die Grundlagen der Graphentheorie behandelt. Die

Graphentheorie ist ein Teilgebiet der Mathematik, findet jedoch auch häufig in der Informatik

Anwendung, da viele algorithmische Probleme auf Graphen zurückgeführt werden können.

Betrachten wir zunächst einige Probleme, die zu graphentheoretischen Problemen führen.

Beispiel 1 (Telefonkette): Die Lehrerin einer Schulklasse plant einen Wandertag. Da die

Abfahrtszeit des hierfür gemieteten Busses sich kurzfristig ändern kann, beschließt sie eine

Telefonkette zu organisieren. Dafür lässt sie sich von allen Schülern sagen, von welchen

anderen Schülern sie die Telefonnummer kennen. Wie soll sie nun festlegen, wer wen anrufen

soll?

Beispiel 2 (Magnetschwebebahn): Angenommen, in Deutschland sollten

Magnetschwebebahnen gebaut werden. Da diese sehr teuer sind, hat man einige große Städte

ausgewählt, die mit dieser neuen Technologie verbunden werden sollen. Auf Grund der hohen

Kosten kann man jedoch auch hier nicht jede dieser Städte mit allen anderen verbinden.

Trotzdem soll es möglich sein (mit Umsteigen) zwischen allen Städten hin- und her zu reisen.

Wie lässt sich dies möglichst kostengünstig realisieren?

Hinweis: Die im folgenden Paragraphen zwei und drei benutzen

Definitionen für gerichtete und ungerichtete Graphen erlauben

jeweils keine Mehrfachkanten zwischen zwei Knoten.

2. Gerichtete Graphen

Def 2.1: Ein gerichteter Graph ist ein Paar G = (V, E) mit einer endlichen Menge V ≠ ∅ und

einer endlichen Menge E ⊆ {(u,v) | u, v ∈ V, u ≠ v}.

Die Elemente von V heißen Knoten (vertex) von G.

Die Elemente von E heißen Kanten (edge) von G.

Abbildung 1

- 2 -

Eine Kante e ∈ E ist also von der Form e = (u, v), wobei u als Anfangsknoten und v als

Endknoten von e bezeichnet wird.

Betrachten wir die Definition anhand eines Beispielgraphen G = (V, E), mit

Abbildung 2

den Knoten V= {1, 2, 3, 4, 5, 6} und den Kanten E = {(1,2), (2,1), (1,3), (2,3), (3,4), (3,5),

(4,5)}. Die Richtung der Pfeile zwischen den Knoten zeigt an, welcher der Anfangs- und

Endknoten ist. Zum Beispiel zeigt der Pfeil zwischen den Knoten 3 und 5 auf den Knoten 5,

weil die Kante (3,5) laut Definition den Anfangsknoten 3 und Endknoten 5 besitzt.

Wenn man einen Graphen zeichnet, ist es egal, welche Form die Knoten haben und wo sie

platziert sind. Ebenso können die Kanten gerade Linien sein oder gekrümmt. Wichtig ist nur,

dass die Struktur des Graphen richtig ist, d.h. dass er die richtige Anzahl an Knoten hat und die

Kanten zwischen den richtigen Knoten verlaufen.

Um die Lesbarkeit einer Zeichnung zu erhöhen, versucht man allerdings meistens die folgenden

Punkte zu berücksichtigen:

- Knoten sollten nicht zu dicht beieinander liegen, da sonst Kanten dazwischen schlecht

erkennbar sind.

- Gleichzeitig sollte der gesamte Graph aber nicht zu groß werden.

- Kanten zeichnet man wenn möglich als gerade Linien und gekrümmt nur dann, wenn

dadurch Schnittpunkte mit anderen Kanten oder Knoten, welche nicht die Endknoten

sind, vermieden werden.

- Ebenso versucht man durch eine geschickte Platzierung der Knoten derartige

Schnittpunkte zu vermeiden, auch wenn dies nicht immer möglich ist.

- 3 -

Bem 2.1: zwei Kanten e1, e2 ∈ E mit e1 = (u, v) und e2 = (v, u) heißen invers.

Def 2.2: Es sei G = (V, E) ein gerichteter Graph.

- Ein Knoten v ∈ V und eine Kante e ∈ E heißen inzident, wenn v der Anfangs- oder

Endknoten von e ist.

- Zwei Kanten e1, e2 ∈ E heißen benachbart oder adjazent, wenn es einen Knoten v ∈ V

gibt, der mit e1 und e2 inzidiert.

- Zwei Knoten u, v ∈ V heißen benachbart oder adjazent, wenn es eine Kante e ∈ E gibt,

die mit u und v inzidiert.

Anhand der Abbildung 2 lässt sich zeigen, dass z.B. in dem Graphen G der Knoten 3 und die

Kante (3,5) inzident sind, da 3 der Anfangsknoten von der Kante ist. Die Kanten (2,3) und (3,5)

sind adjazent, da der Knoten 3 mit beiden Kanten inzidiert. Als letztes Beispiel sind die zwei

Knoten 1 und 2 adjazent, da die Kante (1,2) mit beiden Knoten inzidiert.

Def 2.3: Es sei G = (V, E) ein gerichteter Graph und v ∈ V ein beliebiger Knoten.

Dann bezeichnet man mit g+(v) den Außengrad des Knotens v, d.h. die Anzahl der Kanten e ∈

E mit Anfangsknoten v, und mit g−(v) den Innengrad des Knotens v, d.h. die Anzahl der Kanten

e ∈ E mit Endknoten v. Beides zusammen, also g(v):= g+(v) + g−(v), nennt man den Grad von

v.

So lässt sich folgendes an dem Graphen G in Abbildung 2 berechnen:

g+(1) = 2, g−(1) = 1, g(1) = 3 und g+(4) = 1, g−(4) = 1, g(4) = 2

- 4 -

3. Ungerichtete Graphen

Def 3.1: Ein Graph ist ein Paar G = (V, E) mit einer endlichen Menge V ≠ ∅ und einer endlichen

Menge E ⊆ {{u, v} | u, v ∈ V, v ≠ u}.

Die Elemente von V heißen Knoten von G.

Die Elemente von E heißen Kanten von G.

Eine Kante e ∈ E ist also von der Form e = {u, v} mit gewissen u, v ∈ V, welche als Endknoten

von e bezeichnet werden.

Def 3.2: Es sei G = (V, E) ein gerichteter Graph. Dann heißt G′ = (V, E′) der G zugeordnete

ungerichtete Graph, wenn gilt: E′ = {{u, v}| (u, v) ∈ E}.

Bem 3.1: Umgekehrt kann man auch jedem ungerichteten Graphen G = (V, E) einen gerichteten

Graphen G′ = (V, E′) zuordnen, indem man die Kanten orientiert. Da man eine ungerichtete

Kante immer in zwei Richtungen orientieren kann, ist eine Orientierung G′ nicht eindeutig

bestimmt. Im Gegensatz dazu ist der zugeordnete ungerichtete Graph eindeutig.

Aufg. 3.1: Beschreiben Sie das Haus vom Nikolaus mit einem gerichteten Graphen

G = (V,E).

Lsg 3.1: V = {1, 2, 3, 4, 5}, E = {(1,2), (2,3), (3,4), (4,2), (2,5), (5,1), (1,4), (4,5)} mit folgender

Abbildung 3

Abbildung 3

- 5 -

4. Isomorphie von Graphen

Von isomorphen Graphen ist die Rede, wenn zwei Graphen von der Struktur her gleich sind.

Dabei können isomorphe Graphen unterschiedlich dargestellt werden.

Def 4.1: Zwei Graphen G1 = (V1, E1) und G2 = (V2, E2) heißen isomorph gdw. es eine bijektive

Abbildung p : V1 V2 gibt, so dass folgendes gilt:

Für alle v,w ∈ V1 : {v,w} ∈ E1 {p(v),p(w)} ∈ E2

Wir nennen p dann einen Isomorphismus von G1 auf G2.

Abbildung 4: Zwei isomorphe Graphen G1 und G2 mit p : V1 V2

Zwei Graphen sind genau dann isomorph, wenn der eine Graph aus dem anderen Graphen durch

Umbenennung der Knoten hervorgeht. Zwei Graphen mit der gleichen Knotenzahl, die

gleichartig verbunden sind, sind isomorph. Dabei ist das Erkennung von Isomorphismen nicht

immer einfach.

Abbildung 5

- 6 -

5. Untergraphen

Def 5.1: Sei G = (V, E) ein Graph.

Ein Graph H = (W, F) mit W ⊆ V und F ⊆ E heißt Untergraph (subgraph) von G.

Bem 5.1:

- Gilt W = V, dann heißt H aufspannender Untergraph von G.

- Gilt F = {{v,w}| {v,w} ∈ E und v,w ∈ W}, dann heißt H induzierter Untergraph von

G.

Abbildung 6 Untergraphen eines Graphen G

Allgemeiner gesagt, ein Untergraph heißt aufgespannt, wenn er die gleichen Knoten wie der

Graph besitzt, und induziert, wenn zischen den Knoten, die in dem Untergraphen noch

existieren, alle Kanten wie in dem Hauptgraphen vorhanden sind. Ein Untergraph, der sowohl

aufgespannt als auch induziert ist, ist identisch mit seinem Hauptgraphen.

Def 5.2: Es sei G = (V, E) ein Graph.

Dann heißt der Graph Ĝ = (V, Ē) mit

Ē = {{v, w} | v, w ∈ V, v ≠ w} \ E

Komplementgraph von G.

- 7 -

6. Wege, Kreise und Zusammenhang

Def 6.1: Es sei G = (V, E) ein Graph.

- Eine Folge (v0, v1, . . . , vn) von Knoten mit ei := {vi−1, vi} ∈ E für i = 1, 2, . . . , n heißt

Kantenzug.

- Ein Kantenzug, bei dem die Kanten ei alle verschieden sind, heißt Weg. Die Länge des

Weges ist n.

- Ein Weg heißt einfacher Weg gdw. die Knoten vj paarweise verschieden sind.

Bsp 6.1:

- (a, b, c, a, b, f) ist ein Kantenzug, aber kein Weg.

- (c, b, f, c, d) ist ein Weg, aber kein einfacher Weg.

- (a, b, f, c, d) ist ein einfacher Weg.

Def 6.2: Es sei G = (V,E) ein Graph wie in Def 5.1

- Gilt in einem Kantenzug v0 = vn, so sprechen wir von einem geschlossenen Kantenzug

- Ein Weg, für den v0 = vn gilt heißt Kreis.

- Ein Kreis, bei dem die Knoten vj mit Ausnahme von v0 = vn paarweise verschieden sind,

heißt einfacher Kreis.

Bsp 6.2:

- (a, b, c, a, d, c, a) ist ein geschlossener Kantenzug, aber kein

Kreis.

- (b, c, e, d, c, f, b) ist ein Kreis, aber kein einfacher Kreis.

- (a, b, f, c, a) ist ein einfacher Kreis.

Abbildung 7

Abbildung 7

- 8 -

Def 6.3: Es sei G = (V, E) ein Graph.

Zwei Knoten v, w ∈ V heißen verbindbar gdw. ein Weg von v nach w existiert. G heißt

zusammenhängend gdw. je zwei Knoten von G verbindbar sind.

Daraus folgt, dass der Graph in Abbildung 7 ein zusammenhängender Graph ist, da jeder

Knoten mit einem beliebig anderen verbindbar ist. Der Graph aus Abbildung 2 ist jedoch nicht

zusammenhängend, da der Knoten 6 mit keinem anderen Knoten verbindbar ist, d.h. es existiert

kein Weg von den Knoten 1 bis 5 zu dem Knoten 6.

7. Planare Graphen

Def 7.1: Ein Graph heißt planar, wenn man ihn so zeichnen (man sagt auch: in die Ebene

einbetten) kann, dass sich keine Kanten kreuzen. Ein ebener Graph ist ein planarer Graph

zusammen mit seiner Darstellung in der Ebene.

Bsp 7.1: Ein planarer Graph (links) mit seiner Einbettung (rechts)

Abbildung 8

- 9 -

Bsp 7.2: Der Graph links ist planar. Der Graph rechts ist nicht planar. Sämtliche Versuche, ihn

planar darzustellen, schlagen spätestens an der letzten Kante fehl.

Abbildung 9

8. Färben von Graphen

Def 8.1: Eine Knotenfärbung eines Graphen G = (V, E) mit k Farben ist eine Abbildung

c : V → [k], so dass gilt:

c(u) ≠ c(v) für alle Kanten {u, v} ∈ E

Die chromatische Zahl χ(G) ist die minimale Anzahl Farben, die für eine Knotenfärbung von G

benötigt wird.

Ein Beispiel ist das Färben von politischen Landschaften:

Benachbarte Länder bekommen unterschiedliche Farben. Dies lässt

sich gut an Abbildung 10 darstellen.

Satz 8.1 (Vierfarbensatz): Für jeden planaren Graphen G gilt

χ(G) ≤ 4.

Abbildung 10

- 10 -

9. Quellen- und Literaturverzeichnis

Alexandra Schwartz. Einführung in die Graphentheorie. 2013. Verfügbar unter:

http://www.mathematik.uni-

wuerzburg.de/~schwartz/Lehre/Graphentheorie/SkriptGraphentheorieSchwartz.pdf.

Béla Bollobás. Graph theory, an introductory course. Volume 63 of Graduate Texts in

Mathematics. Springer-Verlag, New York, 1979.

Becker Peter. HS Bonn-Rhein-Sieg. Graphentheorie WS 2014/15. Verfügbar unter:

http://www2.inf.fh-rhein-sieg.de/~pbecke2m/graphentheorie/grundbegriffe2.pdf

Jiang Xiaoyi, Rothaus Kai, Wachenfeld Steffen. Kapitel 6 “Graphentheorie” SS 2007.

Verfügbar unter: http://cvpr.uni

muenster.de/teaching/ss07/diskreteStrukturenSS07/script/DS06.pdf

John M. Harris, Jeffry L. Hirst, and Michael J. Mossinghoff. Combinatorics and graph theory.

Undergraduate Texts in Mathematics. Springer, New York, second edition, 2008.

Abbildung 1: Alexandra Schwartz. Einführung in die Graphentheorie, S. 14

Abbildung 2: Ebenda, S. 16

Abbildung 4: http://de.wikipedia.org/wiki/Isomorphie_von_Graphen

Abbildung 5: http://cvpr.uni

muenster.de/teaching/ss07/diskreteStrukturenSS07/script/DS06.pdf, S. 16

Abbildung 6: HS Bonn-Rhein-Sieg, WS 2014/15. Graphentheorie, S. 5

Abbildung 7: Ebenda, S.11

Abbildung 8: http://cvpr.uni

muenster.de/teaching/ss07/diskreteStrukturenSS07/script/DS06.pdf, S. 20

Abbildung 9: Ebenda, S.21

Abbildung 10: Ebenda, S.30