Eine Eulertour ist ein Weg durch einen Graphen, bei dem jede Kante (Verbindungslinie) genau einmal befahren wird. Der Weg muss an dem Knoten enden, an dem er begonnen hat. Nicht bei jedem Graph ist eine solche Tour möglich. Eine wichtige Voraussetzung für die Möglichkeit einer Eulertour ist, dass alle Knoten eine gerade Anzahl von Kanten haben.
Eulertour finden
Wir wählen zunächst eine unvollständige Tour und notieren sie – d.h. wir suchen uns einen Weg, bei dem wir wieder am Startknoten rauskommen. Anschließend suchen wir uns einen Knoten, an dem noch unbesuchte Kanten vorhanden sind. Von diesem Knoten starten wir wieder eine unvollständige Tour. Zum Schluss schieben wir die 2. Tour in die 1. ein und haben eine vollständige Eulertour.
