Teilpfaden

Teilpfaden, im Deutschen häufig als Subpfade bezeichnet, sind zusammenhängende Abschnitte eines Pfades in einem Graphen oder Netzwerk. Sie entstehen, indem aus einer gegebenen Pfadsequenz hintereinander liegende Teilschritte ausgewählt werden, sodass jeder aufeinanderfolgende Paarknoten durch eine Kante verbunden ist.

Formal lässt sich ein Pfad P in einem Graphen G = (V, E) als eine Sequenz von Knoten P = (v0, v1, ..., vk) definieren, wobei für alle i von 0 bis k-1 die Kante (vi, vi+1) in E gilt (bei gerichteten Graphen in der entsprechenden Richtung). Ein Teilpfad P[i..j] ist dann die Sequenz (vi, vi+1, ..., vj) mit 0 ≤ i ≤ j ≤ k. Die Länge des Teilpfads beträgt j − i; ein Teilpfad kann auch ein einzelner Knoten sein, wenn i = j.

Eigenschaften: Teilpfade sind per Definition Teilsequenzen eines Pfades und behalten die Konnektivität der Reihenfolge. Wenn der Originalpfad einfach (ohne Wiederholungen) ist, bleiben auch seine Teilpfade einfach. In gerichteten Graphen ist die Orientierung des Teilpfads durch die Reihenfolge der Knoten gegeben; in ungerichteten Graphen lässt sich derselbe Teilpfad in Gegenrichtung ebenfalls als gültiger Teilpfad betrachten, sofern die Sequenz entsprechend akzeptiert wird.

Verwandte Konzepte: Teilpfade stehen im Zusammenhang mit dem Konzept der Unterpfade in Algorithmen, bei denen optimale Teilpfade eine Rolle spielen (optimal substructure). Sie dienen in der Praxis dem Routing, der Netzwerkanalyse, der Genomassemblierung sowie der formalen Sprach- und Pfadanalyse.

Zusammenfassung: Teilpfaden sind die Kontiguitätspfade innerhalb eines größeren Pfades, formell als aufeinanderfolgende Knotenabschnitte definiert und in der Theorie sowie Praxis eine zentrale Rolle bei der Analyse von Wegen in Graphen.