Weg (Graphentheorie)

Ein Weg oder eine Kantenfolge ist in der Graphentheorie eine Liste von aufeinander folgenden Knoten, die jeweils durch eine Kante verbunden sind. Ein geschlossener Kantenzug enthält jede Kante nur einmal. Ein Kreis oder Zyklus ist eine spezielle Form des geschlossenen Kantenzugs der zusätzlich jede Ecke nur einmal enthält. Die mathematische Definition des Weges variiert je nach Typ des Graphen. Gelegentlich wird statt der Knotenliste auch die Liste der zusammenhängenden Kanten als Kantenfolge oder Weg bezeichnet.

Ein zentrales Problem in der Graphentheorie ist die Suche nach dem Kürzesten Weg durch einen Graphen.

Näheres unter: Wege, Pfade, Zyklen und Kreise in Graphen