系列平行圖的長方形數與和絃圖數

Abstract

一個圖形G = (V,E)，如果可以找到最小k個和弦圖，則此圖形G = (V,E)的和弦圖數是k。\r\n在這篇論文中，我們呈現存在一個系列平行圖的boxicity是3，且和弦圖數是1或2，存在一個平面圖形的和弦圖數是3。

The chordality of G = (V,E) is dened as the minimum k such that we can write E = E1n...nEk, where each (V,Ei) is a chordal graph.\r\nIn this thesis, we present that (1) there are series-parallel graphs with boxicity 3, (2) there are series-parallel graphs with chordality 1 or 2, and (3) there are planar graphs with chordality 3.

Abstract iii\r\n中文摘要iv\r\n1 The Chordality of a Graph 1\r\n1.1 History of Chordal Graph and Boxicity . . . . . . . 1\r\n1.2 The De nition and Theorems of Chordality . . . . . . 2\r\n1.3 Examples of Chordality . . . . . . . . . . . . . . ..7\r\n2 A Necessary Condition 11\r\n2.1 The Chordality of BPn . . . . . . . . . . . . . . . .11\r\n2.2 The Counter Example . . . . . . . . . . . . . . . . 13\r\n3 Series-Parallel Graphs 14\r\n3.1 The De nition of Treewidth . . . . . . . . . . . . . 14\r\n3.2 The De nition of Series-Parallel Graphs . . . . . . . 17\r\n3.3 The Treewidth and Chordality of Series-Parallel Graphs . . . 22\r\n4 The Boxicity of a Graph 24\r\n4.1 The De nition of Boxicity . . . . . . . . . . . . . ..24\r\n4.2 The Boxicity of Series-Parallel Graphs . . . . . . . 27\r\nReferences 32