Diese Arbeit gibt einen Einblick in die Reichweite von Circle Packings: Es werden tiefer gehende Ergebnisse und Eigenschaften untersucht sowie Existenz und Eindeutigkeit solcher Konstruktionen studiert. Darüber hinaus wird eine Brücke zur Klasse der radial level-planaren Graphen geschlagen. Ein tieferer Einstieg in die Funktionentheorie ist dafür unumgänglich.
Einem planaren Graphen entwende man alle Knoten und definiere sie als Mittelpunkte gewisser disjunkter Kreise. Dass diese Kreise jetzt ganz konkrete Bedingungen erfüllen können, mag überraschend wirken. Es ist möglich, jedem Knoten eines planaren Graphen eine Kreisscheibe (Circle) zuzuweisen, sodass die gesamte Kreispackung (Circle Packing) ein Berührungsmuster erfüllt, welches dem planaren Graphen gleichkommt.
Zwei solche Kreise berühren sich dann und nur dann, wenn die beiden ihren Mittelpunkten zugeordneten Knoten durch eine Kante verbunden sind. Wie Radius und Koordinaten eines jeden Kreises aussehen müssen, um die gewünschten Muster zu erfüllen, ist eine nicht ganz triviale Angelegenheit und bedarf einiges an Arbeit auf dem Gebiet der Circle Packings.
Inhaltsverzeichnis
1. Einführung
1.1. Fragestellung
1.2. Aufbau der Arbeit
2. Planare Graphen
2.1. Grundlagen
2.2. Definitionen
2.3. Eigenschaften planarer Graphen
2.4. Topologischer Exkurs
3. Radiale Level-Planarität
3.1. Level-Graphen
3.2. Radial level-planare Graphen
3.3. Radiale Planaritätstests
3.3.1. Radiale 2-Level-Graphen
3.3.2. Kriterium für nicht-proper-radiale k-Level-Planarität
4. Circle Packings
4.1. Über Circle Packings
4.2. Einführung und Definitionen
4.3. Circle Packing Theorem
4.4. Vorbereitungen zum CPT-Beweis
4.4.1. Label und Radien
4.4.2. Konstruktion der Hilfsdreiecke
4.4.3. Winkel und Winkelsummen
4.4.4. Monotoniekriterien
4.5. Beweis des Circle Packing Theorems
4.6. Eindeutigkeitsaussage des CPTs
5. Circle Packings und Funktionentheorie
5.1. Möbiustransformationen
5.1.1. Inversion bzw. Kreisspiegelung
5.2. Eindeutigkeitsbeweis des CPTs
5.3. Stereographische Projektion
5.4. Inversion eines Circle Packings
5.5. Circle Packings auf der Sphäre
6. Folgerungen und Anwendungen des CPTs
6.1. Planar-Separator-Theorem
6.2. Level-Isolation
7. Schlussbetrachtung
7.1. Fazit, Ausblick, Bewertung
7.2. Zurück zur Graphentheorie
A. Anhang
A.1. Geometrische Umformungen
A.2. Kleinere graphentheoretische Beweise
A.3. Topologische Grundlagen
A.4. Grundlagen der kombinatorischen Geometrie
Zielsetzung & Themen
Die Arbeit untersucht das Verhalten von radial level-planaren Graphen durch die Anwendung von Circle Packings, um festzustellen, ob geometrische Werkzeuge effizientere oder übersichtlichere Lösungen für graphentheoretische Fragestellungen bieten können.
- Untersuchung von planaren Graphen und radialer Level-Planarität
- Einsatz von Circle Packings als geometrisches Hilfsmittel
- Beweis und Eindeutigkeit des Circle Packing Theorems (CPT)
- Anwendung der Funktionentheorie auf Circle Packings
- Analyse radialer Level-Graphen im Kontext von Separator-Theoremen
Auszug aus dem Buch
4.1. Über Circle Packings
Ein Circle Packing ist, kurz ausgedrückt, eine Familie nicht-überlappender Kreisscheiben. Aus dieser einfachen Definition entsteht ein überraschend fruchtbares Feld der Mathematik, das es zu untersuchen gilt.
Historisches: Schon vor einigen hundert Jahren untersuchten Wissenschaftler wie Keppler, Newton oder Gregory das Verhalten von Kugeln und Kreisen im Raum. Wie viele Kugeln passen in eine Kiste vorgegebener Größe? Wie viele gleichgroße Kreise können einen vorgegebenen anderen gleichgroßen Kreis gleichzeitig berühren? Die Liste solcher Fragen ist beliebig erweiterbar. So tat sich dann im Laufe der Zeit auch das Gebiet der Circle Packings auf.
Circle Packings tauchten erstmals in den 1930er-Jahren auf. Paul Koebe studierte sie im Zusammenhang mit konformen Abbildungen (s. [8]). Hiernach gerieten sie einige Zeit in Vergessenheit, bis William Thurston sie in den 1970er-Jahren im Zusammenhang mit hyperbolischen 3-Mannigfaltigkeiten erneut aufgriff (s. [22]). Bei einem Vortrag im Jahre 1985 (s. [23]1) führte er die Circle Packings für ein breiteres Publikum wieder ein, indem er behauptete, dass Abbildungen zwischen Circle Packings zur Approximation konformer Abbildungen benutzt werden könnten. Bewiesen durch Rodin und Sullivan (s. [17]), ist der entstandene Zusammenhang zum Riemannschen Abbildungssatz eine der größten Forschungs-Motivationen auf dem Gebiet der Circle Packings.
In dieser Arbeit soll mit der Graphentheorie ein weiterer Zweig der Mathematik vorgestellt werden, der zur näheren Untersuchung mit Circle Packings motiviert.
Zusammenfassung der Kapitel
1. Einführung: Definition der Zielsetzung und Motivation der Arbeit, die Verbindung von Circle Packings mit der Graphentheorie herzustellen.
2. Planare Graphen: Einführung der graphentheoretischen Grundlagen, Definition planarer Graphen und topologische Betrachtungsweisen.
3. Radiale Level-Planarität: Untersuchung von Level-Graphen in radialer Darstellung und Herleitung von Kriterien für deren Planarität.
4. Circle Packings: Detaillierte geometrische Untersuchung von Circle Packings und Beweis des zentralen Circle Packing Theorems.
5. Circle Packings und Funktionentheorie: Zusammenhang zwischen M-Transformationen, Inversionen und dem Verhalten von Circle Packings in der Ebene sowie auf der Sphäre.
6. Folgerungen und Anwendungen des CPTs: Praktische Anwendung des Circle Packing Theorems für das Planar-Separator-Theorem und weitere graphentheoretische Fragestellungen.
7. Schlussbetrachtung: Zusammenfassende Bewertung der Ergebnisse und Vergleich zwischen graphentheoretischen Methoden und der Theorie der Circle Packings.
A. Anhang: Ergänzende mathematische Herleitungen, Beweise und grundlegende Definitionen aus der Topologie und kombinatorischen Geometrie.
Schlüsselwörter
Circle Packing, Planare Graphen, Level-Planarität, Graphentheorie, Funktionentheorie, Stereographische Projektion, Inversion, Möbiustransformation, Planar-Separator-Theorem, Topologie, Geometrie, Knoten, Kreisscheiben, Sphäre.
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit grundlegend?
Die Arbeit untersucht, ob die Geometrie der sogenannten Circle Packings als Werkzeug dienen kann, um komplexe graphentheoretische Probleme, insbesondere bei radialen Level-Graphen, besser zu lösen.
Was sind die zentralen Themenfelder?
Die zentralen Felder sind die Graphentheorie, die Geometrie von Kreispackungen sowie die Funktionentheorie.
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist es, das Verhalten von radial level-planaren Graphen durch die Theorie der Circle Packings zu analysieren und Kriterien für deren Existenz oder Nicht-Existenz zu formulieren.
Welche wissenschaftlichen Methoden werden angewandt?
Es werden mathematische Beweisverfahren verwendet, darunter geometrische Konstruktionen, graphentheoretische Induktionsbeweise sowie funktionentheoretische Methoden wie Möbiustransformationen.
Was wird im Hauptteil behandelt?
Der Hauptteil befasst sich mit der Definition und dem Beweis des Circle Packing Theorems sowie mit dem Zusammenhang von Kreispackungen und der Funktionentheorie, ergänzt durch Anwendungen wie das Planar-Separator-Theorem.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wesentliche Begriffe sind Circle Packing, Graphentheorie, Level-Planarität, Konformität, Inversion und Topologie.
Was ist ein "maximales Circle Packing"?
Ein Circle Packing wird als maximal bezeichnet, wenn der zugehörige Kontaktgraph ein maximal planarer Graph ist, was bedeutet, dass keine Kante mehr hinzugefügt werden kann, ohne die Planarität zu verletzen.
Welche Rolle spielt die Inversion in diesem Kontext?
Die Inversion (Kreisspiegelung) dient als zentrales Werkzeug, um das Verhalten von Circle Packings zu untersuchen und zeigt, dass die Starrheit von Circle Packings nur bis auf bestimmte Transformationen erhalten bleibt.
Wie unterscheidet sich ein radialer Graph von einem Standard-Level-Graphen?
Bei einem radialen Graphen sind die Ebenen (Levels) nicht horizontal angeordnet, sondern bilden konzentrische Kreise, was die Modellierung gewisser Graphenstrukturen effizienter gestaltet.
- Citation du texte
- M. R. Becker (Auteur), 2013, Circle Packings und Anwendungen. Eine kombinatorische Sichtweise, Munich, GRIN Verlag, https://www.grin.com/document/494665
