PfadVerknüpfung

Pfadverknüpfung, auch Pfadverkettung genannt, bezeichnet in Graphen- und Automata-Theorie die Bildung eines neuen Pfades durch das Verketten zweier gegebener Pfade, sofern der Endpunkt des ersten Pfades mit dem Startpunkt des zweiten Pfades übereinstimmt. Sie ist ein zentrales Grundkonzept zur Beschreibung von Sequenzen von Übergängen in gerichteten Graphen und wird oft verwendet, um Laufbahnen in Zustandsautomaten oder Pfade in Netzwerken zu modellieren.

Formal besteht ein Pfad in einem gerichteten Graphen G=(V,E) aus einer Sequenz von Kanten e1,...,em, die aufeinander folgen und durch die Zwischenknoten verbindend sind. Sei p der Pfad von v0 nach vm und q der Pfad von vm nach vn. Dann ist die Pfadverknüpfung p∘q der Pfad von v0 nach vn, der durch Anhängen der Kanten von q an p entsteht. Die Länge len(p) = m, len(q) = n−m und len(p∘q) = n. Ein Pfad der Länge 0 dient als Identitätspfad am jeweiligen Vertex. Die Verknüpfung ist nur definiert, wenn der Endpunkt des ersten Pfades dem Startpunkt des zweiten Pfades entspricht.

In der Kategorie-Theorie ergibt sich aus der Pfadverknüpfung die freie Kategorie über G: Objekte sind die Knoten, Morphismen die Pfade, und die Komposition entspricht der Pfadverkettung. Identitäten entsprechen triviale Pfade.

Eigenschaften und Beispiele: Die Verknüpfung ist assoziativ; Pfadverknüpfung ist nicht immer eindeutig, wenn es mehrere Kanten zwischen gleichen Knoten gibt. Beispiel: In einem Graphen mit A→B und B→C ergibt die Verknüpfung eines Pfades A→B mit B→C den Pfad A→C.

Anwendungen reichen von Automata-Theorie und formalen Sprachen bis hin zu Netzwerktheorie und Routenplanung. Variantenbezeichnungen umfassen Pfadverkettung, Pfadzusammenführung und Pfadkonkatenation.