Parallelpfaden

Parallelpfaden (auch als Parallelpfade bezeichnet) bezeichnet man in der Graphentheorie mehrere unterschiedliche Pfade zwischen zwei Knoten, die parallel existieren oder als Alternativen dienen. Sie dienen der Redundanz, Lastverteilung oder der Erhöhung der Zuverlässigkeit in Netzen, Transport- oder Robotiksystemen.

Man unterscheidet dabei oft zwischen Pfaden, die Kanten teilen, und solchen, die Knoten teilen. Zwei gängige Arten sind kanten-disjunkte Pfade und knoten-disjunkte Pfade; bei letzteren teilen sich die Pfade keine Zwischenknoten, bei ersteren keine Kanten.

Der Satz von Menger verbindet diese Konzepte mit der minimalen Schnittgröße: Die maximale Anzahl paarweise disjunkter Pfade zwischen zwei Knoten entspricht der minimalen Anzahl von Kanten- oder Knotenschnittstellen, die getrennt werden müssen, um die Verbindung abzubrechen. Damit liefert die Theorie eine Grundlage für die Bewertung der Robustheit von Netzwerken.

Algorithmen: Für zwei disjunkte Pfade gibt es den Suurballe-Algorithmus; für k disjunkte Pfade existieren Yen's- und Eppstein-Algorithmen zur Bestimmung von k-kürzesten Pfaden. Zur Berechnung mehrerer kanten-disjunkter Pfade eignen sich zudem Max-Flow-Modelle, bei denen Kapazitäten entsprechend gewichtet werden.

Anwendungen: Parallelpfaden finden sich in Kommunikations- und Verkehrsnetzen zur Redundanz und Lastverteilung, in der Ressourcen- oder Pfadplanung von Robotern sowie in der Netzwerkanalyse zur Bewertung der Zuverlässigkeit von Verbindungen. Sie ermöglichen alternative Routen, ohne dass ein einzelner Pfad das gesamte System dominiere.