Tittmann Graphentheorie

Eine anwendungsorientierte Einführung
1. aktualisierte Auflage 2011
ISBN: 978-3-446-42853-9
Verlag: Hanser, Carl
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Deutsch, 166 Seiten

Prof. Tittmann hält Vorlesungen zur Mathematik für Ingenieur- und Informatikstudenten an der Hochschule Mittweida.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.leicht verständliche Einführung in das Thema
Zahlreiche Beispiele und Aufgaben
Hervorragend zum Selbststudium geeignetMathematikDieses 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.- Graphen
- Graphen und Matrizen
- Planare Graphen
- Unabhängige Knoten- und Kantenmengen
- Färbungen von Graphen
- Der Zusammenhang von Graphen
- Bäume
- Kreise
- Gerichtete Graphen

Autoren/Hrsg.

Tittmann, Peter

Inhaltsverzeichnis

1;Vorwort;6
2;Inhaltsverzeichnis;8
3;1 Graphen;12
3.1;1.1 Definitionen;13
3.1.1;1.1.1 Knotengrade;14
3.1.2;1.1.2 Wege und Kreise;16
3.1.3;1.1.3 Zusammenhang;16
3.2;1.2 Operationen mit Graphen;17
3.2.1;1.2.1 Entfernen von Knoten und Kanten;17
3.2.2;1.2.2 Fusion und Kontraktion;18
3.2.3;1.2.3 Brücken und Artikulationen;19
3.2.4;1.2.4 Operationen mit Graphen;19
3.3;1.3 Spezielle Graphen;21
3.3.1;1.3.1 Der vollständige Graph;21
3.3.2;1.3.2 Weg und Kreis;22
3.3.3;1.3.3 Bäume;22
3.3.4;1.3.4 Bipartite Graphen;24
3.3.5;1.3.5 Reguläre Graphen;25
3.4;1.4 Isomorphe Graphen;26
3.4.1;1.4.1 Isomorphie;26
3.4.2;1.4.2 Gradfolgen;27
4;2 Graphen und Matrizen;30
4.1;2.1 Die Adjazenzmatrix eines Graphen;30
4.1.1;2.1.1 Potenzen der Adjazenzmatrix;31
4.1.2;2.1.2 Zerlegbare Matrizen;32
4.2;2.2 Die Inzidenzmatrix;33
4.2.1;2.2.1 Die Gradmatrix;34
4.3;2.3 Abstände in Graphen;34
4.3.1;2.3.1 Radius, Durchmesser und Zentrum;35
4.3.2;2.3.2 Die Abstandsmatrix;37
4.4;2.4 Gerüste;38
4.4.1;2.4.1 Die Anzahl der Gerüste;38
4.4.2;2.4.2 Die Admittanzmatrix und der Satz von Kirchhoff;40
5;3 Planare Graphen;44
5.1;3.1 Planare Einbettungen;44
5.1.1;3.1.1 Ebene Kurven und Einbettungen;44
5.1.2;3.1.2 Flächen eines planaren Graphen;46
5.1.3;3.1.3 Einbettungen auf der Kugel;46
5.1.4;3.1.4 Kreuzungszahl und Dicke;47
5.2;3.2 Die Eulersche Polyederformel;48
5.2.1;3.2.1 Polyeder;48
5.2.2;3.2.2 Die Polyederformel für zusammenhängende Graphen;49
5.2.3;3.2.3 Die Polyederformel für nicht zusammenhängende Graphen;51
5.3;3.3 Anwendungen der Polyederformel;51
5.3.1;3.3.1 Nichtplanare Graphen;51
5.3.2;3.3.2 Der Satz von Kuratowski;52
5.3.3;3.3.3 Maximale Kantenzahl planarer Graphen;54
5.3.4;3.3.4 Knotengrade in planaren Graphen;54
5.3.5;3.3.5 Platonische Körper;55
5.4;3.4 Der duale Graph;56
6;4 Unabhängige Knoten- und Kantenmengen;60
6.1;4.1 Unabhängige Knotenmengen;61
6.1.1;4.1.1 Die Unabhängigkeitszahl;61
6.1.2;4.1.2 Cliquen;64
6.1.3;4.1.3 Die Überdeckungszahl;65
6.2;4.2 Matchings;66
6.2.1;4.2.1 Alternierende Wege – der Satz von Berge;67
6.2.2;4.2.2 Der Satz von König;69
6.3;4.3 Der Kantengraph;70
6.4;4.4 Faktoren;72
7;5 Färbungen von Graphen;75
7.1;5.1 Grundlagen;75
7.1.1;5.1.1 Zulässige Färbungen;75
7.1.2;5.1.2 Die chromatische Zahl;76
7.1.3;5.1.3 Schranken für die chromatische Zahl;77
7.2;5.2 Färbungen von planaren Graphen;79
7.3;5.3 Das chromatische Polynom;81
7.3.1;5.3.1 Der vollständige Graph;82
7.3.2;5.3.2 Der Baum;82
7.3.3;5.3.3 Die Dekompositionsgleichung;82
7.3.4;5.3.4 Der Kreis;84
7.3.5;5.3.5 Chromatisches Polynom und chromatische Zahl;85
7.3.6;5.3.6 Partitionen der Knotenmenge;86
7.4;5.4 Eine Anwendung;87
8;6 Der Zusammenhang von Graphen;92
8.1;6.1 Der Knotenzusammenhang;92
8.2;6.2 Der Kantenzusammenhang;95
8.2.1;6.2.1 Schnittmengen;95
8.2.2;6.2.2 Schnitte;96
8.2.3;6.2.3 Die Kantenzusammenhangszahl;97
8.2.4;6.2.4 Knotenzusammenhang und Kantenzusammenhang;97
8.3;6.3 Trennende Knotenmengen;98
8.3.1;6.3.1 Anwendung zur Berechnung der Unabhängigkeitszahl;98
8.3.2;6.3.2 Ein Berechnungsbeispiel;99
8.3.3;6.3.3 Die Berechnung des chromatischen Polynoms;100
8.4;6.4 Partielle k-Bäume;102
8.4.1;6.4.1 k-Bäume;102
8.4.2;6.4.2 Partielle k-Bäume;103
8.4.3;6.4.3 Serien-Parallel-Graphen;104
9;7 Bäume;107
9.1;7.1 Eigenschaften von Bäumen;107
9.1.1;7.1.1 Die Anzahl der Bäume;108
9.1.2;7.1.2 Der Prüfercode und der Satz von Cayley;109
9.1.3;7.1.3 Isomorphieklassen von Bäumen;111
9.2;7.2 Wurzelbäume;111
9.3;7.3 Binäre Bäume;114
10;8 Kreise;118
10.1;8.1 Kreise in Graphen;118
10.1.1;8.1.1 Taille und Umfang;119
10.1.2;8.1.2 Basiskreise;120
10.2;8.2 Hamiltonkreise;121
10.3;8.3 Eulerkreise;124
11;9 Gerichtete Graphen;128
11.1;9.1 Definitionen und Eigenschaften gerichteter Graphen;128
11.1.1;9.1.1 Wege und Erreichbarkeit;129
11.1.2;9.1.2 Zusammenhang und starker Zusammenhang;129
11.1.3;9.1.3 Orientierungen;130
11.1.4;9.1.4 Innen- und Außengrad;131
11.1.5;9.1.5 Quellen und Senken;132
11.1.6;9.1.6 Vektorräume;133
11.1.7;9.1.7 Kozyklen;134
11.1.8;9.1.8 Zyklen- und Kozyklenräume;135
11.2;9.2 Turniere;139
11.3;9.3 Flüsse in Graphen;142
12;Lösungen;147
13;Literaturverzeichnis;159
14;Symbolverzeichnis;161
15;Sachwortverzeichnis;162

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 Ingenieur- und Informatikstudenten an der Hochschule Mittweida.