Eulerian Path & Circuit: Jede Kante genau einmal benutzen

Ein Eulerian Path benutzt jede Kante eines Graphen genau einmal.

Ein Eulerian Circuit erfüllt dieselbe Bedingung und kehrt zusätzlich zum Startknoten zurück.

Eulerian vs Hamiltonian

Eulerian:

jede Edge genau einmal

Hamiltonian:

jeden Vertex genau einmal

Beim Eulerian Path dürfen Knoten mehrfach besucht werden.

Bedingungen für ungerichtete Graphen

Ein Eulerian Circuit existiert, wenn:

• alle nicht isolierten Knoten zusammenhängend sind,
• jeder Knoten geraden Grad besitzt.

Ein Eulerian Path existiert, wenn genau zwei Knoten ungeraden Grad besitzen.

0 ungerade Knoten → Circuit
2 ungerade Knoten → Path
mehr als 2 → kein Eulerian Trail

Hierholzer-Algorithmus

Hierholzer folgt unbenutzten Kanten und fügt Knoten beim Zurückgehen vom Stack zur endgültigen Route hinzu.

function eulerTrailDirected(graph, start) {
  const g = Object.fromEntries(
    Object.entries(graph).map(
      ([node, edges]) => [node, [...edges]]
    )
  );

  const stack = [start];
  const path = [];

  while (stack.length) {
    const current = stack[stack.length - 1];

    if ((g[current]?.length ?? 0) > 0) {
      stack.push(g[current].pop());
    } else {
      path.push(stack.pop());
    }
  }

  return path.reverse();
}

Gerichtete Graphen

Für einen Eulerian Circuit muss bei jedem aktiven Knoten gelten:

inDegree = outDegree

Für einen offenen Eulerian Path gibt es typischerweise einen Startknoten mit einem zusätzlichen Ausgang und einen Endknoten mit einem zusätzlichen Eingang.

Komplexität

Mit geeigneter Datenstruktur:

O(V + E)

Anwendungen

• Straßenreinigung
• Inspektion von Netzwerkverbindungen
• Route Inspection
• Zeichenrätsel ohne Wiederholung einer Linie
• DNA Assembly mit de Bruijn Graphen

Chinese Postman

Der Chinese Postman erlaubt die mehrfache Benutzung bestimmter Kanten und minimiert dabei die Gesamtkosten.

Fazit

Eulerian-Probleme sind kantenorientiert. Hamiltonian-Probleme sind knotenorientiert. Hierholzer ist eine effiziente Standardmethode zur Konstruktion eines Eulerian Trails.