Beschreibung
Der Medialgraph ist eine Konstruktion, die dem Dualgraph sehr ähnlich ist. Hierbei werden bei einem planarem Graphen die Kanten zu Knoten, die unter bestimmten Umständen miteinander verbunden werden.
Definition
Sei ein Planarer Graph. Konstruiere einen neuen Graphen , der einen Knoten für jede Kante hat und einen Kante für zwei Kanten, die eine Ecke einer Zusammenhangskomponente bilden.
Ist so etwas für Zugstrecken nützlich? Man könnte sich eine Abwandlung vorstellen, bei der man Knoten verbindet, wenn sie durch eine Spitze verbunden sind.
Eigenschaften
Eigenschaft