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 Baumweite zu kennen. Ein verwandter Begriff ist die Pfadweite.

Der Begriff wurde 1972 von Umberto Bertelè und Francesco Brioschi eingeführt, unabhängig von Rudolf Halin 1976 und erneut unabhängig von Neil Robertson und Paul Seymour 1984.

Formale Definition

Eine Baumzerlegung von $G=(V,E)$ ist ein Paar $(X,T)$ , wobei $T=(I,F)$ ein Baum ist und $X=\{X_{i}~|~i\in I\}$ eine Familie von Untermengen der Knotenmenge $V$ des Graphen ist, sodass gelten:

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

Die Baumweite der Baumzerlegung $(X,T)$ von $G$ ist definiert als $\max _{i\in I}|X_{i}|-1$ und die Baumweite eines Graphen $G$ ist definiert als die kleinste Baumweite aller Baumzerlegungen von $G$ .

Die Subtraktion von 1 bewirkt, dass die Baumweite von $G$ genau dann 1 beträgt, wenn $G$ ein Baum ist (ohne diese Subtraktion hätten Bäume Baumweite 2).

Erläuterung

Wir verteilen die Knoten von G auf Taschen (Englisch: buckets oder bags), die in einem Baum angeordnet sind, wobei folgende Regeln gelten:

Jeder Knoten aus $V$ ist in mindestens einer Tasche
Die beiden Endknoten jeder Kante sind zusammen in mindestens einer Tasche
Für jeden Knoten $v$ bilden die Taschen, die $v$ enthalten, einen Unterbaum

Eigenschaften

Komplexität

Das Entscheidungsproblem, ob für einen gegebenen Graphen G und eine gegebene Variable k die Baumweite von G höchstens k ist, ist NP-vollständig. Graphen mit einer von einer Konstanten k beschränkten Baumweite lassen sich jedoch in linearer Zeit erkennen. Die Laufzeit dieses Algorithmus hängt linear von Anzahl der Knoten von G und exponentiell von k ab.

Schranken

Es gelten folgende Schranken für Baumweiten:

Jeder Baum mit mindestens 2 Knoten hat eine Baumweite von genau 1.
Jeder Kreisgraph mit mindestens 3 Knoten hat eine Baumweite von genau 2.
Ein Graph ohne Kanten (darunter also auch ein Baum mit 1 Knoten) hat eine Baumweite von genau 0.
Serien-Parallel-Graphen haben eine Baumweite von höchstens 2.
Halingraphen haben eine Baumweite von höchstens 3.
Die Baumweite planarer Graphen ist nicht durch eine Konstante nach oben beschränkt. Dies wird deutlich am Beispiel der $(n\times n)$ -Gittergraphen. Diese besitzen eine Baumweite von $n$ . Die Baumweite von planaren Graphen mit $n$ Knoten ist aber durch $3.182\cdot {\sqrt {n}}$ beschränkt.
Die Baumweite eines Graphen ist höchstens um 1 kleiner als seine größte Clique.

Literatur

Reinhard Diestel: Graphentheorie. 5. Auflage. Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-96134-004-0, 10. Minoren, S. 287–330.
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.
Hans L. Bodlaender: Fixed-Parameter Tractability of Treewidth and Pathwidth. In: Bodlaender H.L., Downey R., Fomin F.V., Marx D. (Hrsg.): The Multivariate Algorithmic Revolution and Beyond. LNCS 7370. Springer, Berlin, Heidelberg 2012, ISBN 978-3-642-30890-1, S. 196–227, doi:10.1007/978-3-642-30891-8_12.

Einzelnachweise

↑ Bertelè, Brioschi, Nonserial Dynamic Programming, Academic Press 1972, dort Dimension genannt
↑ Halin, S-functions for graphs, J. Geom., 8, 1976, 171–186
↑ Robertson, Seymour: Graph minors III: Planar tree-width, Journal of Combinatorial Theory, Series B, Band 36, 1984, S. 49–64
↑ S. Arnborg; D. Corneil; A. Proskurowski: Complexity of finding embeddings in a k-tree. SIAM Journal on Matrix Analysis and Applications, 8 (2) 1987, S. 277–284
↑ Hans L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25 (6) 1996, S. 1305–1317
↑ Fedor V. Fomin, Dimitrios M. Thilikos: New upper bounds on the decomposability of planar graphs. In: Journal of Graph Theory. Band 51, Nr. 1, 2006, S. 53–81, doi:10.1002/jgt.20121.

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

[1] Bertelè, Brioschi, Nonserial Dynamic Programming, Academic Press 1972, dort Dimension genannt

[2] Halin, S-functions for graphs, J. Geom., 8, 1976, 171–186

[3] Robertson, Seymour: Graph minors III: Planar tree-width, Journal of Combinatorial Theory, Series B, Band 36, 1984, S. 49–64

[4] S. Arnborg; D. Corneil; A. Proskurowski: Complexity of finding embeddings in a k-tree. SIAM Journal on Matrix Analysis and Applications, 8 (2) 1987, S. 277–284

[5] Hans L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25 (6) 1996, S. 1305–1317

[6] Fedor V. Fomin, Dimitrios M. Thilikos: New upper bounds on the decomposability of planar graphs. In: Journal of Graph Theory. Band 51, Nr. 1, 2006, S. 53–81, doi:10.1002/jgt.20121.