Pfadoperationen

Pfadoperationen bezeichnen in der Graphentheorie die Operationen, die auf Pfaden in Graphen angewendet werden. Ein Pfad ist eine Folge von Knoten und Kanten, die von einer Start- zu einer Endstelle führt. Je nach Definition kann ein Pfad einfach sein, das heißt Knoten werden nicht wiederholt, oder allgemein auch als Weg verstanden, der Wiederholungen zulässt.

Zu den grundlegenden Pfadoperationen gehört die Verkettung: Hat ein Pfad p1 von v0 nach v1 und ein Pfad p2 von v1 nach vk, so ergibt die Verkettung p1·p2 einen Pfad vom v0 nach vk. Die Umkehrung eines Pfades kehrt die Reihenfolge der Kanten um; sie ist ein Pfad vom Endknoten zum Startknoten, sofern die Kanten in der Gegenrichtung existieren. Teilpfade oder Unterwege beziehen sich auf Segmente eines Pfades und bleiben selbst Pfade, sofern die Verbindungskette gültig bleibt.

Weitere Operationen betreffen Pfadmengen, etwa das Zusammenführen mehrerer Pfade oder das Bilden von Schnittmengen, je nach Kontext unter Berücksichtigung der Richtung in gerichteten Graphen. In der Algorithmik dienen Pfadoperationen der Pfadsuche und -analyse: Pfadexistenztests,Shortest-Path-Abfragen, k-kürzeste Pfade und ähnliche Probleme werden mit entsprechenden Algorithmen wie Dijkstra, Bellman-Ford, Floyd-Warshall oder Yen gelöst. Pfade lassen sich auch dekomponieren, zum Beispiel in Teilpfade, um komplexe Strukturen besser zu analysieren.

Formale Sicht: Die Pfadverkettung bildet eine Monoidstruktur mit dem leeren Pfad als Identität, wobei gerichtete Graphen eine richtungsabhängige Struktur besitzen. Anwendungen finden sich in der Routenplanung, Netzwerkanalyse, Geoinformationssystemen und graphbasierten Abfragesprachen.