Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/96374
|
| Title: | 系列平行圖的長方形數與和絃圖數
The Boxicity and Chordality of a Series-Parallel Graph |
| Authors: | 周佳靜 |
| Contributors: | 張宜武
周佳靜 |
| Keywords: | 和弦圖數
和弦圖
平面圖
系列平行圖
Chordality
Chordal Graphs
Planar Graphs
Series-Parallel Graphs
Boxicity |
| Date: | 2011 |
| Issue Date: | 2016-05-10 19:01:54 (UTC+8) |
| Abstract: | 一個圖形G = (V,E)，如果可以找到最小k個和弦圖，則此圖形G = (V,E)的和弦圖數是k。
在這篇論文中，我們呈現存在一個系列平行圖的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.
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 |
| 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. |
| Description: | 碩士
國立政治大學
應用數學系數學教學碩士在職專班
98972010 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0098972010 |
| Data Type: | thesis |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| index.html | 0Kb | HTML2 | 266 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
