Tittmann Graphentheorie

Eine anwendungsorientierte Einführung
3. aktualisierte Auflage 2019
ISBN: 978-3-446-46503-9
Verlag: Carl Hanser
Format: PDF
Kopierschutz: Wasserzeichen (»Systemvoraussetzungen)

E-Book, Deutsch, 170 Seiten

Dieses Buch liefert eine Einführung in die Graphentheorie - ein Lehrgebiet, das heute nicht nur in der Mathematikausbildung eine große Rolle spielt. Die vielfältigen Anwendungen der Graphentheorie erlangten auch für Informatiker, Wirtschaftler, Chemiker und Ingenieure eine große Bedeutung.


Die ersten acht Kapitel dieses Buches behandeln die Grundlagen der Theorie ungerichteter Graphen. Nach einer Einführung in den Sprachgebrauch der Graphentheorie im ersten Kapitel sind planare Graphen, Unabhängigkeit, Färbungsprobleme, der Zusammenhang von Graphen sowie Bäume und Kreise weitere Schwerpunkte. Das letzte Kapitel befasst sich mit dem Thema gerichtete Graphen.


Die hier vorliegende Einführung in die Graphentheorie entstand aus einer Vorlesungsreihe zur Graphentheorie für Studierende der Computertechnologie und der Angewandten Mathematik an der Hochschule Mittweida.

Autoren/Hrsg.

Tittmann, Peter

Fachgebiete

• Mathematik | Informatik Mathematik Operations Research Graphentheorie

Inhaltsverzeichnis

1;Vorwort;6
2;1 Graphen;12
2.1;1.1 Definitionen;13
2.1.1;1.1.1 Knotengrade;14
2.1.2;1.1.2 Wege und Kreise;16
2.1.3;1.1.3 Zusammenhang;16
2.2;1.2 Operationen mit Graphen;17
2.2.1;1.2.1 Entfernen von Knoten und Kanten;17
2.2.2;1.2.2 Fusion und Kontraktion;18
2.2.3;1.2.3 Bruecken und Artikulationen;19
2.2.4;1.2.4 Operationen mit Graphen;20
2.3;1.3 Spezielle Graphen;21
2.3.1;1.3.1 Der vollständige Graph;21
2.3.2;1.3.2 Weg und Kreis;22
2.3.3;1.3.3 Bäume;22
2.3.4;1.3.4 Bipartite Graphen;24
2.3.5;1.3.5 Regulaere Graphen;25
2.4;1.4 Isomorphe Graphen;26
2.4.1;1.4.1 Isomorphie;26
2.4.2;1.4.2 Gradfolgen;27
2.5;2.4 Spannbaeume;38
2.6;2.4.1 Die Anzahl der Spannbaeume;38
3;2 Graphen und Matrizen;30
3.1;2.1 Die Adjazenzmatrix eines Graphen;30
3.1.1;2.1.1 Potenzen der Adjazenzmatrix;31
3.1.2;2.1.2 Zerlegbare Matrizen;32
3.2;2.2 Die Inzidenzmatrix;33
3.2.1;2.2.1 Die Gradmatrix;34
3.3;2.3 Abstaende in Graphen;34
3.3.1;2.3.1 Radius, Durchmesser und Zentrum;35
3.3.2;2.3.2 Die Abstandsmatrix;37
3.4;2.4 Spannbaeume;38
3.4.1;2.4.1 Die Anzahl der Spannbaeume;38
3.4.2;2.4.2 Die Admittanzmatrix und der Satz von Kirchho;41
4;3 Planare Graphen - die Eulersche Polyederformel;45
4.1;3.1 Planare Einbettungen;45
4.1.1;3.1.1 Ebene Kurven und Einbettungen;45
4.1.2;3.1.2 Flaechen eines planaren Graphen;47
4.1.3;3.1.3 Einbettungen auf der Kugel;47
4.1.4;3.1.4 Kreuzungszahl und Dicke;48
4.2;3.2 Die Eulersche Polyederformel;49
4.2.1;3.2.1 Polyeder;49
4.2.2;3.2.2 Die Polyederformel f?ur zusammenhaengende Graphen;50
4.2.3;3.2.3 Die Polyederformel fuer nicht zusammenhaengende Graphen;52
4.3;3.3 Anwendungen der Polyederformel;52
4.3.1;3.3.1 Nichtplanare Graphen;52
4.3.2;3.3.2 Der Satz von Kuratowski;53
4.3.3;3.3.3 Maximale Kantenzahl planarer Graphen;55
4.3.4;3.3.4 Knotengrade in planaren Graphen;55
4.3.5;3.3.5 Platonische Koerper;56
4.4;3.4 Der duale Graph;57
5;4 Unabhaengige Knoten- und Kantenmengen;61
5.1;4.1 Unabhaengige Knotenmengen;62
5.1.1;4.1.1 Die Unabhaengigkeitszahl;62
5.1.2;4.1.2 Cliquen;65
5.1.3;4.1.3 Die Ueberdeckungszahl;66
5.2;4.2 Matchings;67
5.2.1;4.2.1 Alternierende Wege - der Satz von Berge;68
5.2.2;4.2.2 Der Satz von K?onig;70
5.3;4.3 Der Kantengraph;71
5.4;4.4 Faktoren;73
6;5 Faerbungen von Graphen;77
6.1;5.1 Grundlagen;77
6.1.1;5.1.1 Zulaessige Faerbungen;77
6.1.2;5.1.2 Die chromatische Zahl;78
6.1.3;5.1.3 Schranken fuer die chromatische Zahl;79
6.2;5.2 Faerbungen von planaren Graphen;81
6.3;5.3 Das chromatische Polynom;83
6.3.1;5.3.1 Der vollst?andige Graph;84
6.3.2;5.3.2 Der Baum;84
6.3.3;5.3.3 Die Dekompositionsgleichung;84
6.3.4;5.3.4 Der Kreis;86
6.3.5;5.3.5 Chromatisches Polynom und chromatische Zahl;87
6.3.6;5.3.6 Partitionen der Knotenmenge;87
6.4;5.4 Eine Anwendung;89
7;6 Der Zusammenhang von Graphen;94
7.1;6.1 Der Knotenzusammenhang;94
7.2;6.2 Der Kantenzusammenhang;97
7.2.1;6.2.1 Schnittmengen;97
7.2.2;6.2.2 Schnitte;98
7.2.3;6.2.3 Die Kantenzusammenhangszahl;99
7.2.4;6.2.4 Knotenzusammenhang und Kantenzusammenhang;99
7.3;6.3 Trennende Knotenmengen;100
7.3.1;6.3.1 Anwendung zur Berechnung der Unabhaengigkeitszahl;100
7.3.2;6.3.2 Ein Berechnungsbeispiel;101
7.3.3;6.3.3 Die Berechnung des chromatischen Polynoms;102
7.4;6.4 Partielle k-Baeume;104
7.4.1;6.4.1 k-Baeume;104
7.4.2;6.4.2 Partielle k-Baeume;105
7.4.3;6.4.3 Serien-Parallel-Graphen;106
8;7 Baeume;109
8.1;7.1 Eigenschaften von Baeumen;109
8.1.1;7.1.1 Die Anzahl der Baeume;110
8.1.2;7.1.2 Der Pruefercode und der Satz von Cayley;111
8.1.3;7.1.3 Isomorphieklassen von B?aumen;113
8.2;7.2 Wurzelbaeume;113
8.3;7.3 Binaere Baeume;116
9;8 Kreise;120
9.1;8.1 Kreise in Graphen;120
9.1.1;8.1.1 Taille und Umfang;121
9.1.2;8.1.2 Basiskreise;122
9.2;8.2 Hamiltonkreise;123
9.3;8.3 Eulerkreise;126
9.4;9 Gerichtete Graphen;130
9.4.1;9.1 Definitionen und Eigenschaften gerichteterGraphen;130
9.4.1.1;9.1.1 Wege und Erreichbarkeit;131
9.4.1.2;9.1.2 Zusammenhang und starker Zusammenhang;131
9.4.1.3;9.1.3 Orientierungen;132
9.4.1.4;9.1.4 Innen- und Aussengrad;133
9.4.1.5;9.1.5 Quellen und Senken;134
9.4.1.6;9.1.6 Vektorr?aume;135
9.4.1.7;9.1.7 Kozyklen;136
9.4.1.8;9.1.8 Zyklen- und Kozyklenraeume;137
9.4.2;9.2 Turniere;141
9.4.3;9.3 Fl?usse in Graphen;144
10;Loesungen;149
11;Literaturverzeichnis;163
12;Symbolverzeichnis;165
13;Sachwortverzeichnis;166

Leseproben

- Graphen
- Graphen und Matrizen
- Planare Graphen
- Unabhängige Knoten- und Kantenmengen
- Färbungen von Graphen
- Der Zusammenhang von Graphen
- Bäume
- Kreise
- Gerichtete Graphen

Über Autor(innen)

Prof. Tittmann hält Vorlesungen zur Mathematik für Mathematik- und Informatikstudenten an der Hochschule Mittweida.