Bibliographic Metadata

Title
Angewandte Graphentheorie : Betrachtung von Färbungen, mit speziellem Blick auf die Landkartenfärbung und das daraus resultierende 4-Farben-Problem / vorgelegt von Alina Jannach
Additional Titles
Applied graph theory : examination of colorings, focusing on the coloring of maps and the resulting 4-color problem
AuthorJannach, Alina Cloe
CensorBaur, Karin
PublishedGraz, Mai 2017
DescriptionV, 74 Blätter : Zusammenfassungen (2 Blätter) ; Illustrationen
Institutional NoteKarl-Franzens-Universität Graz, Diplomarbeit, 2017
Annotation
Abweichender Titel laut Übersetzung des Verfassers/der Verfasserin
Zusammenfassungen in Deutsch und Englisch
LanguageGerman
Document typeThesis (Diplom)
Keywords (GND)Graphentheorie / Graphfärbung
URNurn:nbn:at:at-ubg:1-114074 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Angewandte Graphentheorie [2.33 mb]
Links
Reference
Classification
Abstract (German)

In dieser Arbeit wird die Landkartenfärbung aus graphentheoretischer Sicht betrachtet. Die Frage nach der minimalsten Anzahl von Farben für das Färben einer Landkarte der chromatischen Zahl wird gestellt.Dafür werden zuallererst die wichtigsten Definitionen und Grundbegriffe der Graphentheorie erläutert und dargelegt. Anschließend werden die zuvor definierten Eigenschaften von Graphen dazu verwendet, das Königsberger Brückenproblem zu lösen. In weiterer Folge werden planare Graphen definiert und charakterisiert, um im Anschluss überhaupt auf die Färbung von Landkarten eingehen zu können. Für die Charakterisierung wird in dieser Arbeit der Satz von Kuratowski verwendet und ein Anwendungsbeispiel dafür gezeigt. Darauf aufbauend werden die verschiedenen Graphenfärbungen (Knoten-, Kanten- und Listenfärbung) definiert und behandelt. Hierbei wird das Hauptaugenmerk auf die chromatische Zahl gelegt. Anschließend wird das Färben von Landkarten, welche als Dualgraphen dargestellt werden können, gesondert betrachtet. Nach dem Beweis der schwächeren 6- und 5-Farben-Sätze für planare Graphen wird der 4-Farben-Satz eingeführt. Die geschichtliche Entwicklung der Problematik wird genau betrachtet. Dabei wird auch Kempes Beweisversuch behandelt und die Entwicklung des Beweises bis hin zum computerbasierten Beweis von Appel und Haken geschildert. Abgerundet wird diese Arbeit mit den verschiedenen graphentheoretischen Themengebieten, welche sich aus der Arbeit mit dem 4-Farben-Satz entwickelt haben. Dabei wird auf die bereits behandelten Kapitel der planaren Graphen und der Graphenfärbung verwiesen. Die Faktorisierung von Graphen, Hamilton Kreise und Matroide werden dabei noch als Gebiete der Graphentheorie kurz angeschnitten.

Abstract (English)

In graph theory colorings, especially the coloring of maps, are valid topics that have to be investigated from a mathematical point of view. In order to research the smallest number of colors needed for coloring a map, known as the chromatic number, the most important definitions and basic terms of graph theory are outlined. The previously defined characteristics of graphs are then used to solve the Königsberg bridge problem. Subsequently, planar graphs are defined and characterized in order to be able to discuss the coloring of maps. For this characterization the Kuratowski theorem is used and an application example is shown. Based on this, the different graph colorings (vertex, edge and list coloring) can be defined and analyzed, focusing mainly on the chromatic number. Then, the coloring of maps, which can be drawn as a dual graph, will be analyzed and discussed separately. After proving the weaker 6- and 5- color theorems for planar graphs, the 4-color theorem is introduced. The historical development of the problem is closely examined as well: Kempes attempt to prove the 4-color theorem, the development of its proof and the computer-based proof of Appel and Haken are shown and discussed. An overview of various fields of graph theory, which have developed through working with the 4-color theorem, rounds off this paper, referring to earlier discussed chapters of the planar graphs and graph coloring. The factorization of graphs, Hamilton circles, and Matroids, as fields of the graph theory, however, are only briefly mentioned.

Stats
The PDF-Document has been downloaded 49 times.