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.
Zielsetzung und Themenschwerpunkte
Die vorliegende Arbeit befasst sich mit der Untersuchung von Circle Packings im Kontext planarer Graphen, insbesondere von radial level-planaren Graphen. Sie analysiert die Beziehungen zwischen Graphentheorie, Geometrie und Funktionentheorie, die sich durch die Anwendung von Circle Packings auf graphentheoretische Problemstellungen ergeben.
- Definition und Eigenschaften von Circle Packings
- Das Circle Packing Theorem und seine Bedeutung für die Graphentheorie
- Zusammenhang zwischen Circle Packings und radial level-planaren Graphen
- Anwendungen von Circle Packings in der Graphentheorie
- Verbindung von Circle Packings zur Funktionentheorie
Zusammenfassung der Kapitel
- Kapitel 1: Die Einführung stellt die Fragestellung der Arbeit vor, die die Verbindung von Graphentheorie, Geometrie und Circle Packings untersucht.
- Kapitel 2: Dieses Kapitel erläutert grundlegende Konzepte der planaren Graphentheorie, einschließlich Definitionen, Eigenschaften und topologischer Aspekte.
- Kapitel 3: Hier werden radial level-planare Graphen eingeführt, wobei verschiedene Planaritätstests und ihre Eigenschaften diskutiert werden.
- Kapitel 4: Es werden Circle Packings vorgestellt, ihr Zusammenhang mit planaren Graphen erläutert und das Circle Packing Theorem sowie dessen Beweis behandelt.
- Kapitel 5: Die Verbindung von Circle Packings zur Funktionentheorie wird durch die Einführung von Möbiustransformationen, der stereographischen Projektion und der Inversion von Circle Packings hergestellt.
- Kapitel 6: Folgerungen und Anwendungen des Circle Packing Theorems werden behandelt, zum Beispiel das Planar-Separator-Theorem und das Konzept der Level-Isolation.
Schlüsselwörter
Die Arbeit beschäftigt sich mit den Themen Circle Packings, planare Graphen, radial level-planare Graphen, Circle Packing Theorem, Funktionentheorie, Möbiustransformationen, Stereographische Projektion und graphentheoretische Anwendungen.
Häufig gestellte Fragen
Was ist ein Circle Packing?
Ein Circle Packing ist eine Anordnung von Kreisen mit disjunkten Inneren, deren Berührungsmuster einem bestimmten planaren Graphen entspricht.
Was besagt das Circle Packing Theorem (CPT)?
Es besagt, dass für jeden planaren Graphen eine entsprechende Kreispackung existiert, die dessen Struktur (Knoten und Kanten) geometrisch abbildet.
Welche Rolle spielen Möbiustransformationen?
Möbiustransformationen werden in der Funktionentheorie genutzt, um Kreispackungen auf der Sphäre oder in der Ebene zu transformieren und Eindeutigkeitsbeweise zu führen.
Was sind radial level-planare Graphen?
Das sind Graphen, deren Knoten auf konzentrischen Kreisen (Leveln) angeordnet sind, ohne dass sich die Kanten kreuzen.
Wo werden Circle Packings angewendet?
Anwendungen finden sich unter anderem im Planar-Separator-Theorem der Graphentheorie und in der komplexen Analysis zur Approximation konformer Abbildungen.
- Quote paper
- M. R. Becker (Author), 2013, Circle Packings und Anwendungen. Eine kombinatorische Sichtweise, Munich, GRIN Verlag, https://www.grin.com/document/494665
