Pfadweite

Die Pfadweite 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. Pfad- und Baumweite sind größtenteils analog zueinander.

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 G = (V,E) ist ein Paar (X,T), wobei T = (I,F) ein Pfad ist und $X = \{X_i|i \in I\}$ eine Familie von Untermengen von V, eine für jeden Knoten in V, so dass gilt:

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

Erläuterung

Verständlicher ausgedrückt, werden die Knoten von G auf Taschen (englisch: buckets oder bags) verteilt, die in einem Pfad angeordnet sind. Jeder Pfad ist Sonderfall eines Baums (Verzweigungsgrad von 1).

Dabei gelten folgende Regeln:

• Jeder Knoten aus V ist in mindestens einer Tasche,
• die beiden Endknoten jeder Kante sind zusammen in mindestens einer Tasche und
• für jeden Knoten v bilden die Taschen, die v enthalten, einen Unterpfad.

Die Weite w() einer Pfadzerlegung ist die maximale Anzahl Knoten in einer einzelnen Tasche - 1.

Weblinks

• Baum- und Pfadweite – Intuitive Darstellung der Thematik (PDF; 400 kB)
• Nondeterministic Graph Searching: From Pathwidth to Treewidth – Folien unter anderem mit mehreren Zerlegungen (englisch)