pfadmenge

Pfadmenge bezeichnet in der Graphentheorie die Gesamtheit aller Pfade eines Graphen. Ein Pfad ist eine Folge von Knoten v0, v1, ..., vk, so dass für jedes i von 0 bis k−1 das Kantenpaar zwischen vi und vi+1 existiert. In gerichteten Graphen gilt die Richtung der Kanten, d. h. (vi, vi+1) muss in E enthalten sein. In ungerichteten Graphen genügt die Kante {vi, vi+1}.

Die Pfadmenge hängt von der Art der Pfade ab. Man unterscheidet einfache Pfade, bei denen keine Knoten wiederholt werden, von allgemeinen Pfaden, die Zyklen enthalten dürfen. Zudem kann man Pfade nach Start- und Zielknoten klassifizieren oder nach der Länge. In Graphen mit Zyklen ist die Menge aller möglichen Pfade oft unendlich; zur Beschränkung definiert man Pfade beispielsweise mit einer maximalen Länge oder betrachtet nur einfache Pfade.

Repräsentation und Zusammenhang mit Sprachen: Wenn die Kanten mit Symbolen beschriftet sind, erhält jeder Pfad ein Wort über einem Alphabet, dessen Buchstaben den Kanten entsprechen. Die Pfadmenge wirkt damit wie eine Teilmenge der Wortmenge A und steht in engem Zusammenhang mit der Sprachen- und Automaten-Theorie; Pfade von Start- zu akzeptierenden Endzuständen entsprechen akzeptierten Wörtern.

Anwendungen: Pfadmengen spielen eine zentrale Rolle in der Routenplanung, Netzwerktheorie, Graphdatenbanken und in der formalen Verifikation von Programmen. Typische Rechenaufgaben umfassen Pfadsuche, kürzeste Pfade sowie das Zählen oder Enumerieren von Pfaden unter gegebenen Bedingungen. Beispielgraphen illustrieren, wie Pfade gebildet und gezählt werden.