Abschlussarbeit

Länge von Delta-Y-Delta Sequenzen in planaren Graphen

Verfasser/in:
Mathias Schenner
Betreuer/in:
Prof. Dr. André Schulz
Status:
abgeschlossen
Jahr:
2016
Beschreibung:
Delta-Y und Y-Delta Tranformationen sind beliebte Möglichkeiten, einen Graphen schrittweise unter der Beibehaltung einiger seiner Eigenschaften umzubauen. Dabei wird ein Dreieck (Delta) durch ein Grad-3 Knoten (Y) ersetzte und umgekehrt. Man kann auf diese Weise jeden planaren 3-zusammenhängenden Graphen in einen vollständigen Graphen mit 4 Knoten (K4) überführen. Diese Methode bildet das Grundgerüst des Beweises des Satzes von Steinitz, welcher besagt, dass die polyhedrischen Graphen genau die planaren 3-zusammenhängenden Graphen sind. In der Abschlussarbeit soll der Delta-Y-Delta Übergangsgraph untersucht werden. Insbesondere interessieren hierbei kurze Abstände zwischen den Knoten dieses Graphen. Dies soll zum Verständnis der Frage beitragen, wie lang solche Delta-Y-Delta Sequenzen sind, die im K4 enden.

Beschreibung:

Delta-Y und Y-Delta Tranformationen sind beliebte Möglichkeiten, einen Graphen schrittweise unter der Beibehaltung einiger seiner Eigenschaften umzubauen. Dabei wird ein Dreieck (Delta) durch ein Grad-3 Knoten (Y) ersetzte und umgekehrt. Man kann auf diese Weise jeden planaren 3-zusammenhängenden Graphen in einen vollständigen Graphen mit 4 Knoten (K4) überführen. Diese Methode bildet das Grundgerüst des Beweises des Satzes von Steinitz, welcher besagt, dass die polyhedrischen Graphen genau die planaren 3-zusammenhängenden Graphen sind. In der Abschlussarbeit soll der Delta-Y-Delta Übergangsgraph untersucht werden. Insbesondere interessieren hierbei kurze Abstände zwischen den Knoten dieses Graphen. Dies soll zum Verständnis der Frage beitragen, wie lang solche Delta-Y-Delta Sequenzen sind, die im K4 enden.

10.05.2024