Orientierung

 Um gerichtete und ungerichtete Graphen gleich behandeln zu können, wird im Graphenlabor das Konzept der  Orientierung eingeführt. Eine  orientierte Kante $\vec e$ ist ein Paar $(e, d)\in E\cross Dir$ mit $Dir=\{in, out\}$.Dies entspricht der Tatsache, daß man eine Kante aus der Perspektive des End- oder Anfangsknotens betrachten kann.

  

Abbildung: Orientierung von Kanten

Für jede gerichtete oder ungerichtete Kante e ist $\vec e=(e, out)$die normal orientierte oder auch normalisierte Kante. Die  normale Orientierung einer gerichteten Kante ist diejenige Orientierung, bei der man die Kante von ihrem Startknoten aus sieht, bei einer ungerichteten Kante e diejenige Orientierung, bei der man die Kante vom Knoten this(e) aus betrachtet.

Im Graphenlabor werden Kanten mit ihren normal orientierten Kanten identifiziert. Die Funktionen $\alpha$, $\omega$, this und that werden auf die Menge der orientierten Kanten $E\cross Dir$ wie folgt erweitert:

Man beachte, daß die Werte der Funktionen $\alpha$ und $\omega$ von der Orientierung der betrachteten Kante unabhängig sind und nur für gerichtete Graphen sinnvoll sind, und daß die Werte der Funktionen this und that von der Orientierung abhängen. So ist $this(\vec e)$ immer derjenige Knoten, von dem aus man die Kante e gerade betrachtet, und $that(\vec e)$ der Knoten am anderen Ende der Kante.

Insgesamt wird dadurch erreicht, daß zu jedem gerichteten Graph der zugrundeliegende ungerichtete Graph unmittelbar zur Verfügung steht, indem man mit orientierten Kanten arbeitet und auf den gerichteten Graph ausschließlich mit den Funktionen  this,  that zugreift. Soll mit dem Graphenlabor ein ungerichteter Graph verwaltet werden, kann man einen gerichteten Graphen anlegen, dessen zugrundeliegender ungerichteter Graph der gewünschte Graph ist.

Bei der Ausgabe von Graphen wird die Orientierung von Kanten durch das Vorzeichen der Identifikationsnummer ausgedrückt. Ein positives Vorzeichen bedeutet die Orientierung out, ein negatives Vorzeichen die Orientierung in.

In Abschnitt befinden sich Beispielprogramme, die darstellen, wie man orientierte Kanten anwenden kann. Die Methoden zur Verwaltung von orientierten Kanten werden in Abschnitt beschrieben.