Topologische Graphentheorie - Topological graph theory
In der Mathematik ist die topologische Graphentheorie ein Zweig der Graphentheorie . Es untersucht die Einbettung von Graphen in Oberflächen , die räumliche Einbettung von Graphen und Graphen als topologische Räume . Es werden auch das Eintauchen von Graphen untersucht.
Das Einbetten eines Diagramms in eine Oberfläche bedeutet, dass wir das Diagramm auf einer Oberfläche, beispielsweise einer Kugel , zeichnen möchten , ohne dass sich zwei Kanten schneiden. Ein grundlegendes Einbettungsproblem, das häufig als mathematisches Rätsel dargestellt wird, ist das Drei-Häuschen-Problem . Andere Anwendungen finden sich beim Drucken elektronischer Schaltungen, bei denen das Ziel darin besteht, eine Schaltung (das Diagramm) auf eine Leiterplatte (die Oberfläche) zu drucken (einzubetten ), ohne dass sich zwei Verbindungen kreuzen und ein Kurzschluss entsteht .
Graphen als topologische Räume
Einem ungerichteten Graphen können wir einen abstrakten einfachen Komplex C mit einem Einzelelementsatz pro Scheitelpunkt und einem Zweielementsatz pro Kante zuordnen. Die geometrische Realisierung C | des Komplexes besteht aus einer Kopie des Einheitsintervalls [0,1] pro Kante, wobei die Endpunkte dieser Intervalle an Eckpunkten zusammengeklebt sind. In dieser Ansicht sind Einbettungen von Graphen in eine Oberfläche oder als Unterteilungen anderer Graphen beide Beispiele für topologische Einbettung. Der Homöomorphismus von Graphen ist nur die Spezialisierung des topologischen Homöomorphismus , der Begriff eines verbundenen Graphen stimmt mit der topologischen Verbundenheit überein , und ein verbundener Graph ist ein Baum genau dann, wenn seine Grundgruppe trivial ist.
Andere einfache Komplexe, die mit Graphen verbunden sind, umfassen den Whitney-Komplex oder Clique-Komplex mit einer Menge pro Clique des Graphen und den Matching-Komplex mit einer Menge pro Match des Graphen (äquivalent der Clique-Komplex des Komplements des Liniendiagramms ). . Der Übereinstimmungskomplex eines vollständigen zweigeteilten Graphen wird als Schachbrettkomplex bezeichnet , da er auch als Komplex von Sätzen nicht angreifender Türme auf einem Schachbrett beschrieben werden kann.
Beispielstudien
John Hopcroft und Robert Tarjan haben ein Mittel zum Testen der Planarität eines Graphen in einer Zeit abgeleitet, die linear zur Anzahl der Kanten ist. Ihr Algorithmus erstellt dazu eine grafische Einbettung, die sie als "Palme" bezeichnen. Effiziente Planaritätstests sind für das Zeichnen von Diagrammen von grundlegender Bedeutung .
Fan Chung et al. untersuchten das Problem der Einbettung eines Diagramms in ein Buch mit den Eckpunkten des Diagramms in einer Linie entlang des Buchrückens. Die Kanten werden auf separaten Seiten so gezeichnet, dass sich die auf derselben Seite befindlichen Kanten nicht kreuzen. Dieses Problem abstrahiert Layoutprobleme, die beim Verlegen von mehrschichtigen Leiterplatten auftreten.
Graph-Einbettungen werden auch verwendet, um strukturelle Ergebnisse über Graphen mithilfe der Graph-Minor-Theorie und des Graph-Struktur-Theorems zu beweisen .
Siehe auch
- Kreuzungszahl (Graphentheorie)
- Gattung
- Planarer Graph
- Echter Baum
- Ringkurve
- Topologische Kombinatorik
- Spannungsdiagramm