BWL-Lexikon.de
  • Home
  • Grundlagen
    • Aufbau eines Betriebs
    • Definitionen
    • Organisation
    • Personalwirtschaft
    • Planung und Entscheidung
    • Produktionsfaktoren
    • Unternehmensführung
  • BWL
    • Rechtsformen
    • Rechnungswesen
      • Finanzbuchhaltung
      • Kostenarten
      • Jahresabschluss
    • Marketing
    • Logistik
      • Logistik Kennzahlen
      • Beschaffung
      • Lagerverfahren
      • Materialarten
    • Kennzahlen
      • Bilanzkennzahlen
      • Produktivitätskennzahlen
      • Rentabilitätskennzahlen
      • Kennzahlen der GuV
  • VWL
    • Makroökonomie
    • Mikroökonomie
  • Fehler gefunden?

Du bist hier: Startseite » Alle Lektionen » Aufbau eines Betriebs » Planung und Entscheidung » Operations Research » Gerichtete / ungerichtete Graphen

Gerichtete / ungerichtete Graphen

Enthält: Beispiele · Definition · Grafiken · Übungsfragen

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

Toggle
  • Warum sind gerichtete und ungerichtete Graphen wichtig?
  • Was versteht man unter gerichteten und ungerichteten Graphen?
    • Was macht gerichtete Graphen aus?
    • Was macht ungerichtete Graphen aus?
  • Übungsfragen
  • Ergebnisse

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:

Gerichtete Graphen - Aufbau
Gerichtete Graphen – Aufbau
Beispiel
Der Auslieferungsfahrer der “DeliverX AG” muss auf seiner Tagesroute vier Pakete an unterschiedlichen Adressen in der Altstadt ausliefern. Da die Altstadt von engen Gassen geprägt ist, ist ein Großteil davon als Einbahnstraße ausgeschildert.

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.

Gerichtete Graphen - Beispiel
Gerichtete Graphen – Beispiel

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:

Ungerichtete Graphen - Aufbau
Ungerichtete Graphen – Aufbau
Beispiel
Der Auslieferungsfahrer der “DeliverX AG” muss am nächsten Tag wieder vier Pakete an unterschiedliche Adressen ausliefern. Diesmal ist er allerdings im Neubaugebiet der Stadt unterwegs. Hier sind die Straßen breit genug angelegt, sodass es für jede Fahrtrichtung mindestens eine Fahrspur gibt.

Das Straßennetz kann also ungerichteter Graph dargestellt werden:

Ungerichtete Graphen - Beispiel
Ungerichtete Graphen – Beispiel

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.

Übungsfragen

 

#1. Was versteht man unter gerichteten Graphen?

#2. Was versteht man unter ungerichteten Graphen?

#3. Welche Elemente sind grundsätzlich Bestandteil eines Graphen?

#4. “Neben der Richtung von Kanten können Graphen auch in Bezug auf ihre Gewichtung unterschieden werden” – Diese Aussage ist:

#5. “Der Unterschied zwischen gerichteten und ungerichteten Graphen ist für die Lösung betriebswirtschaftlicher Probleme irrelevant.” – diese Aussage ist:

Vorherige
Fertig

Ergebnisse

Share your score!
Tweet your score!
Share to other

Könnte dich auch interessieren:

Inzidenzmatrix bei ungerichteten Graphen

Inzidenzmatrix

In der Inzidenzmatrix werden die Beziehungen der Knoten und der Kanten eines Graphen abgebildet. In diesem Kapitel zeigen wir dir, … weiterlesen >>

Graphentheorie

Graphentheorie

Die Graphentheorie als mathematische Methode befasst sich mit der Untersuchung von Graphen als Darstellung von einer Vielzahl von Problemen. Insbesondere … weiterlesen >>

Adjazenzmatrix bei gewichteten Graphen

Adjazenzmatrix

Die Adjazenzmatrix ist eine Matrix, die die Anzahl der Knoten in einem Graphen und deren Beziehungen zueinander darstellt. Damit lässt … weiterlesen >>

Vollständig bipartiter Graph

Bipartiter Graph

Ein Graph wird dann als bipartit bezeichnet, wenn die enthaltenen Knoten in zwei Teilmengen aufteilbar sind, deren Knoten untereinander keine … weiterlesen >>

Hamiltonkreis

Hamiltonkreis

Wird jeder Knoten in einem Graphen durch einen geschlossenen Pfad durchlaufen und sind Anfangs- und Endpunkt identisch, so spricht man … weiterlesen >>

Nichts passendes dabei?

Erkunde andere Fachbereiche oder benutze die Suchfunktion. Falls Du keine Antwort auf Deine Frage findest, schick uns gerne eine Nachricht, wir versuchen dann passenden Content für Dich zu schaffen.

Zur Übersicht
Oder lieber die Suche benutzen?
  • Eselsbrücke
  • |
  • Buchungssatz
  • |
  • Formeln
  • |
  • Beispiele
  • |
  • Grafiken
  • |
  • Definition
  • |
  • Übungsfragen
  • © BWL-Lexikon.de
  • Datenschutz
  • Impressum
Cookie Einstellungen
Fehler gefunden?

Danke, dass du dir die Zeit nimmst, uns dein Feedback zu geben. Bitte beschreibe so genau wie möglich wo du einen Fehler gefunden hast.