Logo der Fakultät Logo LG Theoretische Informatik
 

Abschlussarbeit

Illustration

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

Verfasser: 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.
03.08.2017
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen