| dc.contributor.advisor | 張宜武 | zh_TW |
| dc.contributor.author (Authors) | 周佳靜 | zh_TW |
| dc.creator (作者) | 周佳靜 | zh_TW |
| dc.date (日期) | 2011 | en_US |
| dc.date.accessioned | 10-May-2016 19:01:54 (UTC+8) | - |
| dc.date.available | 10-May-2016 19:01:54 (UTC+8) | - |
| dc.date.issued (上傳時間) | 10-May-2016 19:01:54 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0098972010 | en_US |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/96374 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 應用數學系數學教學碩士在職專班 | zh_TW |
| dc.description (描述) | 98972010 | zh_TW |
| dc.description.abstract (摘要) | 一個圖形G = (V,E)，如果可以找到最小k個和弦圖，則此圖形G = (V,E)的和弦圖數是k。 在這篇論文中，我們呈現存在一個系列平行圖的boxicity是3，且和弦圖數是1或2，存在一個平面圖形的和弦圖數是3。 | zh_TW |
| dc.description.abstract (摘要) | 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. In 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. | en_US |
| dc.description.abstract (摘要) | Abstract iii 中文摘要iv 1 The Chordality of a Graph 1 1.1 History of Chordal Graph and Boxicity . . . . . . . 1 1.2 The De nition and Theorems of Chordality . . . . . . 2 1.3 Examples of Chordality . . . . . . . . . . . . . . ..7 2 A Necessary Condition 11 2.1 The Chordality of BPn . . . . . . . . . . . . . . . .11 2.2 The Counter Example . . . . . . . . . . . . . . . . 13 3 Series-Parallel Graphs 14 3.1 The De nition of Treewidth . . . . . . . . . . . . . 14 3.2 The De nition of Series-Parallel Graphs . . . . . . . 17 3.3 The Treewidth and Chordality of Series-Parallel Graphs . . . 22 4 The Boxicity of a Graph 24 4.1 The De nition of Boxicity . . . . . . . . . . . . . ..24 4.2 The Boxicity of Series-Parallel Graphs . . . . . . . 27 References 32 | - |
| dc.description.tableofcontents | Abstract iii 中文摘要iv 1 The Chordality of a Graph 1 1.1 History of Chordal Graph and Boxicity . . . . . . . 1 1.2 The Denition and Theorems of Chordality . . . . . . 2 1.3 Examples of Chordality . . . . . . . . . . . . . . ..7 2 A Necessary Condition 11 2.1 The Chordality of BPn . . . . . . . . . . . . . . . .11 2.2 The Counter Example . . . . . . . . . . . . . . . . 13 3 Series-Parallel Graphs 14 3.1 The Denition of Treewidth . . . . . . . . . . . . . 14 3.2 The Denition of Series-Parallel Graphs . . . . . . . 17 3.3 The Treewidth and Chordality of Series-Parallel Graphs . . . 22 4 The Boxicity of a Graph 24 4.1 The Denition of Boxicity . . . . . . . . . . . . . ..24 4.2 The Boxicity of Series-Parallel Graphs . . . . . . . 27 References 32 | zh_TW |
| dc.format.extent | 3975360 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0098972010 | en_US |
| dc.subject (關鍵詞) | 和弦圖數 | zh_TW |
| dc.subject (關鍵詞) | 和弦圖 | zh_TW |
| dc.subject (關鍵詞) | 平面圖 | zh_TW |
| dc.subject (關鍵詞) | 系列平行圖 | zh_TW |
| dc.subject (關鍵詞) | Chordality | en_US |
| dc.subject (關鍵詞) | Chordal Graphs | en_US |
| dc.subject (關鍵詞) | Planar Graphs | en_US |
| dc.subject (關鍵詞) | Series-Parallel Graphs | en_US |
| dc.subject (關鍵詞) | Boxicity | en_US |
| dc.title (題名) | 系列平行圖的長方形數與和絃圖數 | zh_TW |
| dc.title (題名) | The Boxicity and Chordality of a Series-Parallel Graph | en_US |
| dc.type (資料類型) | thesis | en_US |
| dc.relation.reference (參考文獻) | [1] P. Buneman, A characterization of rigid circuit graphs, Discrete Mathematics, 9 (1974), pp. 205-212. [2] M. Cozzens and F. Roberts, On dimensional properties of graphs, Graphs and Combinatorics, 5 (1989), pp. 29-46. [3] G. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc., 27 (1952), pp. 85-92. [4] R. Duffin, Topology of series-parallel nextworks, J. Math. Anal. Appl., 10(1965), pp. 303-318. [5] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory (B), 16 (1974), pp. 47-56. [6] M. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press,(1980). [7] T. A. McKee and E. R. Scheinerman, On the chordality of a graph, Graph Theory, 17 (1993), pp. 221-232. [8] E. Scheinerman, Intersection classes and multiple intersection parameters of graphs, Ph.D. thesis, Princeton University, (1984). [9] C. Thomassen, Interval representations of planar graphs, Journal of Combinatorial Theory (B), 40 (1986), pp. 9-20. [10] J. Walter, Representations of chordal graphs as subtrees of a tree, J. Graph Theory, 2 (1978), pp. 265-267. | zh_TW |
