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

Hamiltonkreis

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

Wird jeder Knoten in einem Graphen durch einen geschlossenen Pfad durchlaufen und sind Anfangs- und Endpunkt identisch, so spricht man von einem Hamiltonkreis. Die Untersuchung eines Graphen nach der Existenz eines solchen Pfades stellt ein wichtiges Problem in der Graphentheorie dar.

Wir erklären dir in diesem Abschnitt was man unter einem Hamiltonkreis versteht und wann er eine Rolle spielt. Außerdem zeigen wir dir, wann und wie der Hamiltonkreis genutzt werden kann. Mit den anschließenden Übungsaufgaben kannst du dein gelerntes Wissen überprüfen.

Synonym: hamiltonischer Kreis

Inhalt dieser Lektion

  • Warum ist der Hamiltonkreis wichtig?
  • Was versteht man unter dem Hamiltonkreis?
    • Sonderfall: der Hamiltonweg
  • Weitere Form eines Zyklus im Graphen: Der Eulerkreis
    • Sonderfall: der Eulerweg
  • Übungsfragen

Warum ist der Hamiltonkreis wichtig?

Die Frage nach der Existenz eines Hamiltonkreises in einem Graphen kann für die Lösung einer Vielzahl von betriebswirtschaftlichen Problemen genutzt werden. So ist beispielsweise die Routenplanung in der Logistik eine der Anwendungsmöglichkeiten

Was versteht man unter dem Hamiltonkreis?

Sind der Anfangs- und Endpunkt eines Pfades in einem Graphen gleich, so spricht man von einem Zyklus. Der Hamiltonkreis ist eine Sonderform eines solchen Zyklus. Er beschreibt den Pfad in einem Graphen, welcher am gleichen Knoten beginnt und endet, wobei er jeden Knoten des Graphen durchläuft.

Die Suche nach der Existenz eines Hamiltonkreises in einem Graphen wird als Hamiltonkreisproblem bezeichnet. Gemäß der Unterscheidung nach gerichteten und ungerichteten Graphen kann auch das Hamiltonkreisproblem in ein gerichtetes und ungerichtetes unterschieden werden.

Hamiltonkreis
Hamiltonkreis
Beispiel
Das Problem des Handlungsreisenden stellt ein typisches Hamiltonkreisproblem dar. Hierbei soll der Handlungsreisende mehrere Städte besuchen und am Ende wieder in seiner Heimatstadt ankommen. Dabei darf jede Stadt nur einmal besucht werden. Es wird also ein Hamiltonkreis in dem entsprechenden Graphen gesucht.

Sonderfall: der Hamiltonweg

Synonym: Hamiltonscher Weg

Genau wie beim Hamiltonkreis beschreibt auch der Hamiltonweg einen Pfad in einem Graphen, der jeden Knoten einmal durchläuft. Allerdings sind hierbei der Anfangs- und Endknoten nicht identisch. Existiert in einem Graphen G ein Hamiltonweg aber kein Hamiltonkreis, so bezeichnet man den Graphen als semihamiltonisch.

Weitere Form eines Zyklus im Graphen: Der Eulerkreis

Synonym: Eulerscher Kreis

Neben dem Hamiltonkreis beschreibt auch der Eulerkreis eine besondere Form eines Zykluses in einem Graphen. Im Gegensatz zum Hamiltonkreis stehen hierbei aber weniger die Knoten im Mittelpunkt als vielmehr die Kanten. Von einem Eulerkreis spricht man, wenn innerhalb des Zyklus jede Kante im Graphen genau einmal genutzt wird.

Beispiel
Ein typisches Beispiel für den Eulerkreis ist das bekannte Königsberger Brückenproblem. Die einzelnen Stadtteile der Stadt Königsberg sind durch einen Fluss getrennt.

Dieser kann über sieben Brücken überquert werden. Gesucht wird ein Rundgang durch die Stadt, bei der jede Brücke genau einmal überquert wird. Leonhard Euler bewies im Jahr 1736, dass ein solcher Rundgang nicht möglich ist.

Er fand heraus, dass ein Eulerkreis nur möglich ist, wenn höchstens in zwei der Knotenpunkte ein ungerader Knotengrad existiert. Beim Problem der Königsberger Brücken jedoch besitzt jeder der Knoten einen ungeraden Knotengrad. Demnach kann ein Eulerkreis und damit auch kein entsprechender Rundgang durch die Stadt existieren.

Sonderfall: der Eulerweg

Synonym: Eulerscher Weg

Bei einem Eulerweg sind der Anfangs- und Endknoten nicht identisch, dennoch werden alle Kanten im Graphen genutzt. Das bekannte Kinder-Zeichenspiel „Das Haus vom Nikolaus“ beschreibt einen Eulerweg.

Übungsfragen

#1. Was versteht man unter einem Hamiltonkreis?

#2. Was versteht man unter einem Eulerkreis?

#3. “Das “Problem des Handlungsreisenden ist ein typisches Beispiel für die Suche nach einem Hamiltonkreis in einem Graphen” - diese Aussage ist:

#4. “Das Königsberger Brückenproblem kann durch einen Eulerkreis gelöst werden. ” - Diese Aussage ist:

#5. “Das “Haus vom Nikolaus beschreibt einen typischen Euler Weg.” - diese Aussage ist:

Fertig

Ergebnis

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

Dijkstra Algorithmus - Anwendungsbeispiel

Dijkstra Algorithmus

Der Dijkstra Algorithmus gehört zur Gruppe der Greedy Algorithmen. Er dient der Berechnung des kürzesten Pfades in einem Graphen von … weiterlesen >>

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

Graphentheorie

Graphentheorie

Die Graphentheorie als mathematische Methode befasst sich mit der Untersuchung von Graphen als Darstellung von einer Vielzahl von Problemen. Insbesondere … 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.