Gerichtete und ungerichtete Graphen sind Elemente der Graphentheorie, einer mathematischen Methode zur Lösung einer Vielzahl von algorithmischen Problemen. Der Unterschied zwischen beiden besteht darin, dass gerichtete Graphen nur in einer Richtung genutzt werden können, bei ungerichteten jedoch keine Richtung vorgegeben ist.
Wir zeigen dir in diesem Abschnitt, warum gerichtete und ungerichtete Graphen wichtig sind und welche Bedeutung sie in der betrieblichen Anwendung haben. Abschließend kannst du dein Wissen anhand einiger Übungsaufgaben überprüfen.
Inhalt dieser Lektion
Warum sind gerichtete und ungerichtete Graphen wichtig?
Die Graphentheorie als ein Teilgebiet der Mathematik kann auch zur Untersuchung und Lösung betriebswirtschaftlicher Fragestellungen und Probleme herangezogen werden. Dabei kann die Richtung der Graphen eine entscheidende Rolle zur Herangehensweise und Lösung des Problems spielen. Aus diesem Grund ist bei der Untersuchung des aufgestellten Graphenmodells wichtig darauf zu achten, ob es sich um einen gerichteten oder ungerichteten Graphen handelt.
Was versteht man unter gerichteten und ungerichteten Graphen?
In der Graphentheorie besteht ein ein Graph G immer aus den folgenden Elementen:
- der Menge von Knoten V
- der Menge von Kanten E
Zur Entstehung eines Graphen sind die jeweiligen Knotenpunkte immer durch entsprechende Kanten miteinander verbunden. Je nach Art der Kanten kann man zwischen gerichteten und ungerichteten Graphen unterscheiden.
Was macht gerichtete Graphen aus?
In gerichteten Graphen haben die Kanten zwischen den Knoten die Eigenschaft, dass sie nur in bestimmte Richtungen genutzt werden können. Hierbei werden die Kanten als Pfeile dargestellt, um die Richtung in der sie genutzt werden können abzubilden:
Die Wege können also nur in eine Richtung befahren werden. Um die optimale Route zu planen, stellt er das Straßennetz als gerichteten Graph dar. Start- und Endpunkt ist jeweils das Depot des Unternehmens. Außerdem soll jede Adresse nur einmal angefahren werden.
Anhand des gerichteten Graphen ist zu erkennen, dass die erste logische Route Depot → A → B → C → D → Depot nicht möglich ist, da die Kante zwischen den Knoten C und D in dieser Richtung nicht genutzt werden kann. Die einzig mögliche Route, die alle Bedingungen für die Auslieferung der Pakete erfüllt, ist demnach Depot → A → D → C → B → Depot.
Was macht ungerichtete Graphen aus?
Im Gegensatz zu gerichteten Graphen spielt bei ungerichteten Graphen die Richtung der Kanten keine Rolle.
Sie können in beide Richtungen genutzt werden und werden daher als einfache Verbindungslinie dargestellt:
Das Straßennetz kann also ungerichteter Graph dargestellt werden:
Es gibt diesmal also verschiedene Möglichkeiten, die Pakete auszuliefern. Um die bestmögliche Route wählen zu können, müsste der Auslieferungsfahrer noch eine weitere Eigenschaft von Graphen in Betracht ziehen: die Gewichtung. Hierbei unterscheidet man zwischen gewichteten und ungewichteten Graphen.
Bei gewichteten Graphen sind die Kanten unterschiedlich lang, ungewichtete haben gleiche Kantenlängen oder die Länge der Kanten ist für die Betrachtung irrelevant. In unserem Beispiel würde die Kantenlänge also die Wege-Kilometer zwischen den einzelnen Adressen darstellen. Mit Hilfe dieser Angabe könnte der Auslieferungsfahrer die kürzeste Route ermitteln, welche als optimal anzusehen ist.
