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.