Pfadzerlegung

Pfadzerlegung bezeichnet in der Graphentheorie die Zerlegung der Kantenmenge eines Graphen G = (V,E) in eine endliche Menge P von Pfaden, so dass jedes Element von E genau in einem Pfad aus P vorkommt. Die Pfade sind einfache Pfade und paarweise kanten-disjunkt; das heißt, jedes Kante gehört genau zu einem Pfad. Oft wird zusätzlich verlangt, dass die Pfade bestimmte Längenbeschränkungen erfüllen oder dass gerichtete Graphen berücksichtigt werden, wobei die Pfade die Orientierung respektieren. Werden auch geschlossene Kreise zugelassen, spricht man von einer Zerlegung in Pfade und Zyklen.

Beispiele: Ein Pfadgraph P_n besitzt eine Pfadzerlegung in einen einzigen Pfad der Länge n−1. Ein Kreis C_n lässt sich in zwei Pfade zerlegen: einen Pfad der Länge n−1 und einen Pfad der Länge 1.

Verwendungen: Pfadzerlegungen dienen der Strukturierung von Kantenmengen in Anwendungen der Netzwerktheorie, Verkehrsplanung, Bioinformatik und algorithmischer Graphentheorie. Sie ermöglichen das Aufteilen komplexer Netze in einfache Bausteine zur Analyse, zum Routing oder zur parallelen Verarbeitung.

Beziehung zu verwandten Konzepten: Die Pfadzerlegung unterscheidet sich von der Pfaddeckung, bei der alle Knoten statt Kanten abgedeckt werden. Zyklen spielen in vielen Kontexten eine Rolle, insbesondere in Variationen, die geschlossene Pfade zulassen.