簡易檢索 / 詳目顯示
| 研究生： |
周佳靜 |
|---|---|
| 論文名稱： |
系列平行圖的長方形數與和絃圖數 The Boxicity and Chordality of a Series-Parallel Graph |
| 指導教授： | 張宜武 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系數學教學碩士在職專班 |
| 論文出版年： | 2011 |
| 畢業學年度： | 100 |
| 語文別： | 英文 |
| 論文頁數： | 32 |
| 中文關鍵詞： | 和弦圖數 、和弦圖 、平面圖 、系列平行圖 |
| 外文關鍵詞： | Planar Graphs, Series-Parallel Graphs, Boxicity |
| 相關次數： | 點閱：217 下載：18 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
一個圖形G = (V,E)，如果可以找到最小k個和弦圖，則此圖形G = (V,E)的和弦圖數是k。
在這篇論文中，我們呈現存在一個系列平行圖的boxicity是3，且和弦圖數是1或2，存在一個平面圖形的和弦圖數是3。
The chordality of G = (V,E) is de ned 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.
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
[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.
