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 » Graphentheorie

Graphentheorie

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

Die Graphentheorie als mathematische Methode befasst sich mit der Untersuchung von Graphen als Darstellung von einer Vielzahl von Problemen. Insbesondere in der Logistik und dem Projektmanagement kommen die praktischen Anwendungsmöglichkeiten der Graphentheorie zum Zuge.

In diesem Kapitel erfährst du, warum die Graphentheorie wichtig ist und was sie ausmacht. Anhand der nachfolgenden Übungsaufgaben kannst du dein Wissen testen und dich auf deine nächste Prüfung vorbereiten.

Inhalt dieser Lektion

Toggle
  • Warum ist die Graphentheorie wichtig?
  • Was versteht man unter der Graphentheorie?
    • Unterscheidungen bei Graphen
      • Gerichtete und ungerichtete Graphen
      • Zusammenhängende und nicht zusammenhängende Graphen
      • Gewichteten und ungewichteten Graphen
    • Knotengrad bei Graphen
      • Knotengrad bei gerichteten Graphen
      • Knotengrad bei ungerichteten Graphen
  • Anwendung der Graphentheorie
  • Übungsfragen
  • Ergebnisse

Warum ist die Graphentheorie wichtig?

Als Teilgebiet der Mathematik untersucht die Graphentheorie die Eigenschaften von Graphen und deren Beziehungen zueinander. Was auf den ersten Blick als abstrakte und stark theoretische Betrachtung erscheint, kann tatsächlich Lösungsansätze für eine Vielzahl von alltäglichen und betriebsrelevanten Problemen liefern.

Neben den Wirtschaftswissenschaften findet die Graphentheorie auch in der Informatik Anwendung, da sich eine Vielzahl von algorithmischen Problemen mittels Graphentheorie lösen lassen.

Was versteht man unter der Graphentheorie?

Ein “Graph G” besteht grundsätzlich aus folgenden Bestandteilen:

  • Menge an Knoten V
  • Menge an Kanten E

Zwei Knoten werden dabei immer von einer Kante verbunden. Dabei kann man unterschiedliche Arten von Graphen unterscheiden.

Unterscheidungen bei Graphen

Grundsätzlich kann zwischen gerichteten und ungerichteten Graphen unterschieden werden. Dabei unterscheiden sich die Graphen in der Eigenschaft der jeweiligen Kanten zwischen den Knoten.

Gerichtete und ungerichtete Graphen

  • Gerichtete Graphen:
    Die Kanten, welche die einzelnen Knoten verbinden, sind als Pfeil dargestellt. Somit kann die Kante nur in entsprechend der Pfeilrichtung genutzt werden.
  • Ungerichtete Graphen:
    Hierbei können die Kanten des Graphen als Verbindung zwischen den Knoten in beide Richtungen genutzt werden.
Graphentheorie
Graphentheorie

Zusammenhängende und nicht zusammenhängende Graphen

Neben der Unterscheidung zwischen gerichteten und ungerichteten Graphen ist auch der Zusammenhang des Graphen zu betrachten:

  • zusammenhängende Graphen:
    Von jedem Knotenpaar aus ist jeder beliebige Knoten erreichbar. Als schwach zusammenhängend bezeichnet man einen Graphen, bei dem durch die Richtung der Kanten ein Knotenpunkt nicht erreichbar ist. Können alle Knoten auch unter Beachtung der Richtungen der Kanten erreicht werden, spricht man von einem stark zusammenhängenden Graphen.
  • nicht zusammenhängende Graphen:
    Verfügt der Graph über isolierte Knoten oder Knotengruppen, ist also nicht jeder Knoten erreichbar, so handelt es sich um einen nicht zusammenhängenden Graphen.

Gewichteten und ungewichteten Graphen

Ein weiterer Unterschied besteht in gewichteten und ungewichteten Graphen:

  • gewichtete Graphen:
    Die Längen der einzelnen Kanten sind unterschiedlich und müssen berücksichtigt werden.
  • ungewichtete Graphen:
    Die Kantenlängen zwischen den Knotenpunkten sind gleich lang oder die Länge spielt keine Rolle in der Betrachtung.

Knotengrad bei Graphen

Der Knotengrad gibt die Anzahl der ein- bzw. ausgehenden Kanten an einem Knotenpunkt an. Auch hierbei unterscheidet man zwischen gerichteten und ungerichteten Graphen.

Knotengrad bei gerichteten Graphen

Bei gerichteten Graphen, also denjenigen, deren Kanten nur bestimmte Richtungen erlauben, ist zwischen dem Eingangsgrad und dem Ausgangsgrad zu unterscheiden. Der Eingangsgrad bezeichnet dabei die Anzahl der eingehenden Kanten, der Ausgangsgrad die Anzahl der ausgehenden Kanten.

Der Eingangsgrad wird dabei als erstes genannt, als zweites der Ausgangsgrad. Besitzt ein Knoten keine eingehenden Kanten sondern nur ausgehende, so wird dieser als Quelle bezeichnet. Knoten, die keine ausgehenden Kanten und nur eingehende aufweisen, nennt man Senke.

Ein gerichteter Graph mit Angabe des Knotengrades könnte folgendermaßen aussehen:

Graphentheorie: Knotengrad bei gerichteten Graphen
Graphentheorie: Knotengrad bei gerichteten Graphen

Knotengrad bei ungerichteten Graphen

Bei ungerichteten Graphen spielt die Richtung der Kanten keine Rolle. Daher wird auch nicht zwischen Eingangs- und Ausgangsgrad unterschieden. Der Knotengrad gibt daher die Anzahl aller an den Knotenpunkt anschließenden Kanten an. Die Knoten werden daher auch als benachbarte Knoten bezeichnet.

Dies könnte folgendermaßen aussehen:

Graphentheorie: Knotengrad bei ungerichteten Graphen
Graphentheorie: Knotengrad bei ungerichteten Graphen

Anwendung der Graphentheorie

Die Erkenntnisse der Graphentheorie können für eine Vielzahl von Problemlösungen genutzt werden. Ein typisches Beispiel ist das bekannte “Problem des Handlungsreisenden”.

Beispiel
Der Vertreter der “Glasklar AG” möchte in verschiedenen Städten mögliche neue Kunden besuchen, um Vertragsabschlüsse zu künftigen Geschäftsbeziehungen vorzubereiten. Dabei soll die möglichst effektivste Route gefunden werden – unter der Bedingung, dass jeder Ort nur einmal besucht werden darf und er am Ende wieder in seiner Heimatstadt ankommt. Als Graph dargestellt könnte dies folgendermaßen aussehen:

Graphentheorie
Graphentheorie

Zur Lösung dieses Problems stehen unterschiedliche Methoden zur Verfügung, insbesondere Algorithmen, die es erlauben unter möglichst wenig Aufwand die bestmögliche Route zu finden.

Diese sind beispielsweise:

  • der Greedy Algorithmus
  • der Dijkstra Algorithmus
  • der Kruskal Algorithmus
  • der Prim Algorithmus
  • der Bellmann Ford Algorithmus
  • die Ungarische Methode.

Übungsfragen

 

#1. Was versteht man unter der Graphentheorie?

#2. Welche Elemente sind Bestandteil eines Graphen in der Graphentheorie?

#3. Was ist der Unterschied zwischen gerichteten und ungerichteten Graphen?

#4. “In der Graphentheorie kann zwischen gewichteten und ungewichteten Kanten unterschieden werden” – Diese Aussage ist:

#5. “Der Knotengrad eines Graphen gibt die Menge der Knoten an, die sich im gesamten Graphen befinden. ” – diese Aussage ist:

Vorherige
Fertig

Ergebnisse

Share your score!
Tweet your score!
Share to other

Könnte dich auch interessieren:

Gerichtete Graphen - Beispiel

Gerichtete / ungerichtete Graphen

Gerichtete und ungerichtete Graphen sind Elemente der Graphentheorie, einer mathematischen Methode zur Lösung einer Vielzahl von algorithmischen Problemen. Der Unterschied … weiterlesen >>

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 >>

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 >>

Hamiltonkreis

Hamiltonkreis

Wird jeder Knoten in einem Graphen durch einen geschlossenen Pfad durchlaufen und sind Anfangs- und Endpunkt identisch, so spricht man … 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 >>

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.