Pfadweite

Begriff aus der Graphentheorie

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

Bearbeiten

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

Eine Pfadzerlegung von   ist ein Paar  , wobei   ein Pfad ist und   eine Familie von Untermengen von  , eine für jeden Knoten in  , so dass gilt:

  •  .
  • Für alle Kanten   gibt es ein   mit  .
  • Für alle   gilt, wenn   auf dem Pfad von   zu   in   ist, dann  .

Erläuterung

Bearbeiten

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   ist in mindestens einer Tasche,
  • die beiden Endknoten jeder Kante sind zusammen in mindestens einer Tasche und
  • für jeden Knoten   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

Bearbeiten
  • 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.