Pfadweite

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


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Baumweite — Die Baumweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie baum ähnlich ein Graph ist. Da viele Algorithmen auf Bäumen (oder Baumzerlegungen) effizient laufen, die dies auf allgemeinen Graphen nicht tun, ist es interessant, die… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”