imported>Leyo: redundant zu DOI

2026-04-08T18:57:36Z

redundant zu DOI

Neue Seite

Die '''Baumweite''' ist ein Begriff aus der [[Graphentheorie]]. Sie sagt aus, wie <q>baum-ähnlich</q> ein [[Graph (Graphentheorie)|Graph]] ist. Da viele [[Algorithmus|Algorithmen]] auf [[Baum (Graphentheorie)|Bäumen]] effizient laufen, die dies auf allgemeinen Graphen nicht tun, ist es interessant, die Baumweite und eine zugehörige minimale [[Baumzerlegung (Graphentheorie)|Baumzerlegung]] eines Graphen zu kennen. Ein verwandter Begriff ist die [[Pfadweite]].

Der Begriff wurde 1972 von Umberto Bertelè und Francesco Brioschi<ref>Bertelè, Brioschi, Nonserial Dynamic Programming, Academic Press 1972, dort ''Dimension'' genannt</ref> eingeführt, unabhängig von [[Rudolf Halin]] 1976<ref>Halin, S-functions for graphs, J. Geom., 8, 1976, 171–186</ref> und erneut unabhängig von [[Neil Robertson (Mathematiker)|Neil Robertson]] und [[Paul Seymour (Mathematiker)|Paul Seymour]] 1984<ref>Robertson, Seymour: Graph minors III: Planar tree-width, Journal of Combinatorial Theory, Series B, Band 36, 1984, S. 49–64</ref>.

== Formale Definition ==
Eine ''Baumzerlegung'' eines Graphen
<math>G = (V,E)</math> ist ein Paar
<math>(X,T)</math>, wobei
<math>T = (I,F)</math> ein Baum und
<math>X = \{X_i~|~i \in I\}</math> eine [[Familie (Mathematik)|Familie]] von Untermengen der [[Knoten (Graphentheorie)|Knotenmenge]]
<math>V</math> des Graphen ist, sodass folgende Bedingungen gelten, wobei 3 und 4 Äquivalent<ref>{{Literatur |Autor=Hans L. Bodlaender, Arie M. C. A. Koster |Titel=Treewidth computations I. Upper bounds |Sammelwerk=Information and Computation |Band=208 |Nummer=3 |Datum=2010-03-01 |ISSN=0890-5401 |DOI=10.1016/j.ic.2009.03.008 |Seiten=259–275}}</ref> zueinander sind:

# <math>\bigcup_{i \in I} X_i = V</math>.
# Für alle [[Kante (Graphentheorie)|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>.
# Für alle <math>v \in V</math> induziert die Menge <math>I_v = \{i \in I| v \in X_i\}</math> einen zusammenhängenden Teilbaum in <math>T</math>.

Die ''Weite der Baumzerlegung'' <math>(X,T)</math> von <math>G</math> ist definiert als <math>\max_{i\in I} |X_i|-1</math> und die ''Baumweite'' <math>\operatorname{tw}(G)</math> eines Graphen <math>G</math> ist definiert als die kleinste Weite aller möglichen Baumzerlegungen von <math>G</math>.

Die Subtraktion von 1 in dieser Definition bewirkt, dass Bäume (und Wälder) die Baumweite 1 haben.
Ohne diese Subtraktion hätten nur Graphen ohne Kanten die Baumweite 1.

=== 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 <math>V</math> ist in mindestens einer Tasche.
# Die beiden Endknoten jeder Kante sind zusammen in mindestens einer Tasche.
# Für eine Tasche <math>X</math>, die auf einem beliebigen Pfad liegt und zwei beliebige Taschen <math>Y</math> und <math>Z</math> auf jenem Pfad, sind die gemeinsamen Knoten der Taschen<math>Y,Z</math> auch in <math>X</math> enthalten.
# Für jeden Knoten <math>v</math> bilden die Taschen, die <math>v</math> enthalten, einen zusammenhängenden Teilbaum.

== Eigenschaften ==
=== Komplexität ===
Das [[Entscheidbar|Entscheidungsproblem]], ob für einen gegebenen Graphen ''G'' und eine gegebene Variable ''k'' die Baumweite von ''G'' höchstens ''k'' ist, ist [[NP-Vollständigkeit|NP-vollständig]].<ref>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</ref> Graphen mit einer von einer Konstanten ''k'' beschränkten Baumweite lassen sich jedoch in linearer Zeit erkennen.<ref>Hans L. Bodlaender: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25 (6) 1996, S. 1305–1317</ref> Die Laufzeit dieses Algorithmus hängt linear von der Anzahl der Knoten von ''G'' und exponentiell von ''k'' ab. Damit erfüllt jener Algorithmus das Kriterium für parametrisierte Probleme und das Baumweite Problem liegt in der Komplexitätsklasse [[Parametrisierter Algorithmus|FPT]].

=== 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-Graph]]en haben eine Baumweite von höchstens 2.
* [[Rudolf Halin|Halingraphen]] haben eine Baumweite von höchstens 3.
* Die Baumweite [[Planarer Graph|planarer Graphen]] ist nicht durch eine Konstante nach oben beschränkt. Dies wird deutlich am Beispiel der <math>(n \times n)</math>-[[Gittergraph]]en. Diese besitzen eine Baumweite von <math>n</math>. Die Baumweite von planaren Graphen mit <math>n</math> Knoten ist aber durch <math>3,\!182 \cdot \sqrt{n}</math> beschränkt.<ref>{{Literatur|Autor=Fedor V. Fomin, Dimitrios M. Thilikos |Titel=New upper bounds on the decomposability of planar graphs |Sammelwerk=Journal of Graph Theory |Band=51 |Nummer=1 |Datum=2006 |Seiten=53–81 |DOI=10.1002/jgt.20121}}</ref>
* Die Baumweite eines Graphen ist mindestens so groß wie seine größte [[Clique (Graphentheorie)|Clique]] minus 1.

== Berechnung ==
Zur Berechnung der Baumweite eines Graphen existieren mehrere Algorithmen, darunter gibt es kombinatorische Ansätze, wie den Bodländer Algorithmus<ref>{{Literatur |Autor=Hans L. Bodlaender |Titel=A linear time algorithm for finding tree-decompositions of small treewidth |Sammelwerk=Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing |Verlag=Association for Computing Machinery |Ort=New York, NY, USA |Datum=1993-06-01 |Reihe=STOC '93 |ISBN=978-0-89791-591-5 |DOI=10.1145/167088.167161 |Seiten=226–234 |Online=https://dl.acm.org/doi/10.1145/167088.167161 |Abruf=2025-10-03}}</ref> oder ganzzahlige lineare Ansätze<ref>{{Literatur |Autor=Sven Mallach |Titel=On integer linear programs for treewidth based on perfect elimination orderings (extended version) |Sammelwerk=Acta Informatica |Band=62 |Nummer=3 |Datum=2025-08-26 |ISSN=1432-0525 |DOI=10.1007/s00236-025-00505-y |Seiten=34 }}</ref>. Allen Ansätzen ist gemein, dass sie nur für ''kleine'' Instanzen, bzw. ''kleine'' und beschränkte Baumweite <q>''schnelle''</q> Ergebnisse liefern.

=== Preprocessing ===
Das Preprocessing beschreibt eine Vorberechnung, vor der Ausführung des eigentlichen Lösungsalgorithmus. Ziel ist es dabei, die gegebene Graphen Instanz zu verkleinern/reduzieren, damit der Hauptalgorithmus auf jener kleineren Instanz schneller eine Lösung finden kann. Beim Preprocessing wird die gesuchte Eigenschaft (hier Baumweite) nicht verändert oder bereits eine Lösung ausgegeben.

Für das Baumweite Problem existieren Preprocessing Regeln, die hierarchisch aufeinander stehen und in der Lage sind, Graphen bis zu einer Baumweite von 3 zu erkennen oder eine reduzierte Instanz mit Baumweite von mindestens 4 zu erzeugen.<ref name=":0">{{Literatur |Autor=Hans L. Bodlaender and Arie M.C.A. Koster and Frank van den Eijkhof and Linda C. van der Gaag |Titel=Pre-processing for Triangulation of Probabilistic Networks |Hrsg=ZIB |Ort=Berlin |Datum=2001 |Seiten=01-39}}</ref>

==== Baumweite 0 ====
[[Datei:Treewidth rule0.svg|mini|right|Anwendung von Regel 0]]
Reduktionsregel 0: Inselchen Regel (engl. Islet rule) Sei <math>v</math> ein Knoten mit Grad 0. Entferne <math>v</math>.

==== Baumweite 1 ====
[[File:Treewidth reduction rule 1.svg|thumb|Anwendung von Regel 1]]
Reduktionsregel 1: Zweig-Regel (engl. Twig rule) Sei <math>v</math> ein Knoten mit Grad 1. Entferne <math>v</math>.

==== Baumweite 2 ====
[[File:Reduction rule 2 for treewdith.svg|thumb|Anwendung von Regel 2]]
Reduktionsregel 2: Serien Regel (engl. Series rule) Sei <math>v</math> ein Knoten mit Grad 2. Füge eine Kante zwischen den Nachbarn von <math>v</math> ein, falls sie noch nicht existiert. Entferne <math>v</math>.

==== Baumweite 3 ====
[[File:Reduction for 3a for treewidth.svg|thumb|Anwendung von Regel 3a]]
Reduktionsregel 3a: Dreiecks Regel (engl. Triangle rule) Sei <math>v</math> ein Knoten mit Grad 3, wobei mindestens zwei Nachbarn durch eine Kante miteinander verbunden sind. Vervollständige die 3 Nachbarn von <math>v</math> zu einer Clique. Entferne <math>v</math>.

[[File:Reduction rule 3b for treewidth.svg|thumb|Anwendung von Regel 3b]]
Reduktionsregel 3b: Kumpel Regel (engl. Buddy rule) Seien <math>v,w</math> Knoten mit Grad 3 mit den gleichen Nachbarn. Vervollständige die 3 Nachbarn von <math>v</math> und <math>w</math> zu einer Clique. Entferne <math>v</math> und <math>w</math>.

[[File:Reduction rule 3c for treewidth.svg|thumb|Anwendung von Regel 3c]]
Reduktionsregel 3c: Würfel Regel (engl. Cube rule) Seien <math>a,b,c,d,x,v,w</math> Knoten, die Knoten <math>a,b,c,d</math> besitzen Grad 3, <math>C = (a,v,b,x,c,w,a)</math> ist ein <math>6</math>-Kreis und <math>a,b,c</math> sind mit <math>d</math> verbunden. Vervollständige <math>v,w,x</math> zu einer Clique. Entferne <math>a,b,c,d</math>.

Aus der Anwendung der Preprocessing Regeln lassen sich folgende Aussage ableiten:

Für einen Graphen <math>G</math> wende die Preprocessing Regeln zwischen <math>0</math> und <math>k, k \in \{0,1,2,3\}</math> an, bis dies nicht mehr möglich ist.
Erhält man als Endergebnis den leeren Graphen, so gilt <math>\operatorname{tw}(G) \leq k</math>, erhält man nicht den leeren Graphen, so gilt für den entstandenen Graphen <math>G'</math>, als auf für <math>G</math> die Ungleichung <math>\operatorname{tw}(G),\operatorname{tw}(G') > k</math>.<ref name=":0" />

== Literatur ==
* {{Literatur
| Autor=Reinhard Diestel
| Titel=Graphentheorie
| Auflage=5. Auflage
| Verlag=Springer-Verlag
| Ort=Berlin, Heidelberg
| Datum=2010
| Seiten=287–330
| Kapitel=10. Minoren
| ISBN=978-3-96134-004-0}}
* {{Literatur
| Autor=Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke
| Titel=Exakte Algorithmen für schwere Graphenprobleme
| Verlag=Springer-Verlag
| Ort=Berlin, Heidelberg
| Datum=2010
| ISBN= 978-3-642-04499-1}}
* {{Literatur
|Autor=Hans L. Bodlaender
|Titel=Fixed-Parameter Tractability of Treewidth and Pathwidth
|Hrsg=Bodlaender H.L., Downey R., Fomin F.V., Marx D.
|Sammelwerk=The Multivariate Algorithmic Revolution and Beyond
|Band= LNCS 7370
|Verlag= Springer
|Ort= Berlin, Heidelberg
|Datum= 2012
|ISBN=978-3-642-30890-1
|Seiten=196–227
|DOI=10.1007/978-3-642-30891-8_12}}

== Einzelnachweise ==
<references />
[[Kategorie:Grundbegriff (Graphentheorie)]]

Baumweite - Versionsgeschichte

imported>Leyo: redundant zu DOI