Pfadausdehnung

Pfadausdehnung bezeichnet in der Graphentheorie den Prozess, einen bestehenden einfachen Pfad in einem Graphen durch das Hinzufügen weiterer Knoten und Kanten an einem oder beiden Enden zu verlängern, sodass die Folge der Scheitelpunkte weiterhin eine einfache Pfadfolge bleibt. Formal sei G = (V,E) ein Graph und P = v0, v1, ..., vk ein Pfad in G. Eine Erweiterung am rechten Ende besteht darin, einen Knoten u ∈ N(vk) zu wählen, der noch nicht in {v0, ..., vk} vorkommt, so dass P' = v0, v1, ..., vk, u ein Pfad ist. Analog kann am linken Ende ein neuer Knoten w ∈ N(v0) gewählt werden, sodass P'' = w, v0, v1, ..., vk ein Pfad wird. Erweiterungen an beiden Enden sind ebenfalls möglich, sofern die resultierenden Folgen einfache Pfade bleiben.

Ein Pfad, der sich nicht mehr verlängern lässt, wird als maximaler Pfad bezeichnet. In endlichen Graphen kann es mehrere maximale Pfade geben; der längste Pfad eines Graphen (mit größter Gesamtlänge) wird als längster Pfad bezeichnet, und falls er alle Scheitelpunkte des Graphen umfasst, spricht man von einem Hamiltonpfad.

Anwendungen: Pfadausdehnung findet Nutzung in Such- und Enumerationsverfahren, bei Greedy- oder Backtracking-Strategien zur Ermittlung längerer oder optimaler Pfade. Die Bestimmung des längsten Pfades ist im Allgemeinen NP-schwer; in bestimmten Graphklassen, wie DAGs, lässt sich das Problem jedoch polynomial lösen.

Beispiele: In einem Quadratgraph A-B-C-D-A lässt sich der Pfad A-B durch eine Erweiterung am Ende zu A-B-C oder A-B-D verlängern, sofern die entsprechenden Knoten noch nicht verwendet wurden.

Siehe auch: Pfad, Hamiltonpfad, längster Pfad, Pfadproblem.