Pfadweite

Die Pfadweite oder Wegweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie „pfad-ähnlich“ ein Graph ist. Da viele Algorithmen auf Pfaden (oder Pfadzerlegungen) effizient laufen, die dies auf allgemeinen Graphen nicht tun, ist es interessant, die Pfadweite zu kennen. Ein verwandter Begriff ist die Baumweite.

Formale Definition

Die Pfadweite eines Graphen G ist definiert als die kleinste Weite aller Pfadzerlegungen (Baumzerlegungen, die einen Pfad bilden) von G.

Eine Pfadzerlegung von ${\displaystyle G=(V,E)}$ ist ein Paar ${\displaystyle (X,T)}$, wobei ${\displaystyle T=(I,F)}$ ein Pfad ist und ${\displaystyle X=\{X_{i}|i\in I\}}$ eine Familie von Untermengen von ${\displaystyle V}$, eine für jeden Knoten in ${\displaystyle I}$, so dass gilt:

• ${\displaystyle \bigcup _{i\in I}X_{i}=V}$.
• Für alle Kanten ${\displaystyle (v,w)\in E}$ gibt es ein ${\displaystyle i\in I}$ mit ${\displaystyle v,w\in X_{i}}$.
• Für alle ${\displaystyle i,j,k\in I}$ gilt, wenn ${\displaystyle j}$ auf dem Pfad von ${\displaystyle i}$ zu ${\displaystyle k}$ in ${\displaystyle T}$ ist, dann ${\displaystyle X_{i}\cap X_{k}\subseteq X_{j}}$.

Erläuterung

Verständlicher ausgedrückt, werden die Knoten des Graphen auf Taschen (englisch: buckets oder bags) verteilt, die in einem Pfad aufeinanderfolgend angeordnet sind.

Dabei gelten folgende Regeln:

• Jeder Knoten aus ${\displaystyle V}$ ist in mindestens einer Tasche,
• die beiden Endknoten jeder Kante sind zusammen in mindestens einer Tasche und
• für jeden Knoten ${\displaystyle v\in V}$ folgen alle Taschen, die ihn enthalten, unmittelbar nacheinander.

Die Weite einer Pfadzerlegung ist die maximale Anzahl von Knoten in einer einzelnen Tasche minus 1.

Literatur

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer-Verlag, Berlin Heidelberg 2010, ISBN 978-3-642-14911-5.
• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme, Springer-Verlag, Berlin Heidelberg, 2010, ISBN 978-3-642-04499-1.