圖之和弦圖數與樹寬

Abstract

對於任何一個圖G = (V;E) ，如果我們可以找到最少的k 個弦圖(V;Ei)，使得E = E1 \\ \\ Ek ，則我們定義此圖G = (V;E) 的chordality為k ；而一個圖G = (V;E) 的樹寬則被定義為此圖所有的樹分解的寬的最小值。在這篇論文中，最主要的結論是所有圖的chordality 會小於或等於它的樹寬；更特別的是，有一些平面圖的chordality 為3，而所有系列平行圖的chordality 頂多為2。

The chordality of a graph G = (V;E) is dened as the minimum k such that we can write E = E1 \\ \\ Ek, where each (V;Ei) is a chordal graph. The treewidth of a graph G = (V;E) is dened to be the minimum width over all tree decompositions of G. In this thesis, the principal result is that the chordality of a graph is at most its treewidth. In particular, there are planar graphs with chordality 3, and series-parallel graphs have chordality at most 2.

Abstract ii\r\n中文摘要iii\r\n1 Introduction 1\r\n1.1 History of Chordality and Treewidth 1\r\n1.2 The De nition of Chordality and Treewidth 2\r\n2 The Chordality of a Graph 6\r\n2.1 Theorems and Examples of Chordality 6\r\n2.2 The Counter Example 14\r\n3 The Treewidth of a Graph 15\r\n3.1 The Treewidth of Some Classes of Graphs 15\r\n3.2 The Chordality of K2;2;2 22\r\n4 Chordality vs. Treewidth 23\r\n4.1 The Weaker Inequality between Chordality and Treewidth 23\r\n4.2 Chordality Bounded by Its Treewidth 24\r\n4.3 The Chordality of Series{Parallel Graphs 37\r\nReferences 38