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 $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 $I$ , 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 des Graphen auf Taschen (englisch: buckets oder bags) verteilt, die in einem Pfad aufeinanderfolgend angeordnet sind.

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\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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.