imported>Maxeto0910: Kleinere Anpassungen

2020-04-09T22:01:07Z

Kleinere Anpassungen

Neue Seite

Die '''Pfadweite''' oder '''Wegweite''' ist ein Begriff aus der [[Graphentheorie]]. Sie sagt aus, wie „[[Pfad (Graphentheorie)|pfad]]-ähnlich“ ein [[Graph (Graphentheorie)|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 <math>G = (V,E)</math> ist ein Paar <math>(X,T)</math>, wobei <math>T = (I,F)</math> ein Pfad ist und <math>X = \{X_i|i \in I\}</math> eine Familie von Untermengen von <math>V</math>, eine für jeden Knoten in <math>I</math>, so dass gilt:

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

== 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 <math>V</math> ist in mindestens einer Tasche,
* die beiden Endknoten jeder Kante sind zusammen in mindestens einer Tasche und
* für jeden Knoten <math>v \in V </math> 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.

[[Kategorie:Grundbegriff (Graphentheorie)]]

Pfadweite - Versionsgeschichte

imported>Maxeto0910: Kleinere Anpassungen