Titelaufnahme

Titel
Tree decomposition : graph minor theory and algorithmic implications / von Miriam Heinz
VerfasserHeinz, Miriam
Begutachter / BegutachterinDrmota, Michael
Erschienen2013
UmfangIV, 70 S. : graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2013
SpracheEnglisch
DokumenttypDiplomarbeit
URNurn:nbn:at:at-ubtuw:1-65513 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Tree decomposition [0.74 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Diese Arbeit behandelt das Konzept der Baumzerlegung eines Graphen und seine Anwendungen in der Minorentheorie. Der Begriff Baumweite wird als Kennzahl für den globalen Zusammenhang eines Graphen eingeführt. Weiters werden Clique-Summen, (partielle) k-Bäume und chordale Graphen vorgestellt und in Zusammenhang mit Baumzerlegungen gesetzt. Es wird gezeigt, dass für jeden planaren Graphen G die Baumweite aller Graphen, die G nicht als Minor enthalten, durch einen von G abhängigen Wert beschränkt ist. Der präsentierte Beweis basiert auf Vereinfachungen des Beweises des Minorensatzes von Neil Robertson und P. D. Seymour. Abschließend werden Anwendungen von Baumzerlegungen behandelt, beispielsweise ein Algorithmus für das k-disjunkte-Pfade-Problem. Auch Resultate aus dem Bereich der Pursuit-Evasion-Games auf Graphen und der Berechnung von Baumweite werden vorgestellt.

Zusammenfassung (Englisch)

The focus of this thesis is the concept of tree-decomposition of graphs and its applications to graph minor theory. The notions of tree-decomposition and tree-width are presented along with how tree-width measures global connectivity properties of a corresponding graph. We introduce clique-sums, (partial) k-trees, and chordal graphs and their relation to tree-decomposition. It is shown that every graph not containing some planar graph as a minor has bounded tree-width. The proof is based on simplifications of the proof of the graph minor theorem by Neil Robertson and P. D. Seymour. Applications of tree-decomposition such as an algorithm for the k disjoint paths problem and results concerning graph searching are discussed. We also give some information about the computation of tree-width.