簡易檢索 / 詳目顯示
| 研究生： |
李則旻 Lee, Tse Min |
|---|---|
| 論文名稱： |
有關有弦探測圖形的探討 Some Problems on Chordal Probe Graphs |
| 指導教授： | 張宜武 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 2013 |
| 畢業學年度： | 101 |
| 語文別： | 英文 |
| 論文頁數： | 33 |
| 中文關鍵詞： | 有弦圖形 、有弦深測圖形 |
| 外文關鍵詞： | Chordal Graphs, Chordal Probe Graphs |
| 相關次數： | 點閱：193 下載：0 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在這篇論文中，我們探討有弦探測圖形與三方星狀圖、完美有序圖、
排列圖的關係。另外我們給一些有弦探測圖形的例子並找到一個有弦
探測圖形的必要的條件。最後我們探討一些有關有弦探測圖與其他圖
的包含關係。
1 Introduction 1
2 Some definitions and examples of graphs 4
2.1 Interval graphs and Interval probe graphs . . . . . . . . . . . . . . 4
2.2 Chordal graphs, Chordal probe graphs, and Weakly chordal graphs 6
2.3 Asteroidal triple graphs (AT graphs) . . . . . . . . . . . . . . . . . 7
2.4 Transitive orientations and Comparability graphs . . . . . . . . . . 7
2.5 Alternately orientable graphs . . . . . . . . . . . . . . . . . . . . . 8
2.6 Perfectly orderable graphs . . . . . . . . . . . . . . . . . . . . . . . 9
2.7 Permutation graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.8 Perfect graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.9 2+2+2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Chordal probe graphs and other classes of graphs 12
3.1 Chordal probe graphs and asteroidal triple graphs . . . . . . . . . . 12
3.2 Chordal probe graphs and perfectly orderable graphs . . . . . . . . 16
3.3 Chordal probe graphs and permutation graphs . . . . . . . . . . . . 20
3.4 Some examples of chordal probe graphs and a necessary condition of
being a chordal probe graph . . . . . . . . . . . . . . . . . . . . . 24
4 Other classes of graphs containing the class of chordal probe graphs 28
4.1 Hierarchy of classes of chordal probe graphs . . . . . . . . . . . . . 28
4.2 Some containment relationships between chordal probe graphs and
other classes of graphs . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Open Problems and Further Directions of Studies 32
Bibliography 33
[1] J. P. S. Andreas Brandstädt, Van Bang Le, Graph classes: A survey,
SIAM Monographs on Discrete Math. and Applications, (1999).
[2] C. Berge and e. Chvatal, Topics on perfect graphs, Annals of discrete
mathematics, 21 (1984).
[3] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic
Press, 1980.
[4] R. B. Hayward, Weakly triangulated graphs, Journal of Combinatorial Theory,
Series B, 39 (1985), pp. 200–208.
[5] C. G. Lekkerkerker and J. C. Boland, Representation of a finite graph
by a set of intervals on the real line, Fundamenta Mathematicae, 51 (1962),
pp. 45–64.
[6] L. L. M. Grotschel and A. Schrijver, The ellipsoid method and its consequences
in combinatorial optimization, Combinatorica, 1 (1981), pp. 169–197.
[7] A. N. T. Martin Charles Golumbic, Tolerance Graphs, Cambridge University
Press, 2004.
[8] M. L. Martin Charles Golumbic, Chordal probe graphs, Discrete Applied
Mathematics, 143 (2004), pp. 221–237.
[9] L. L. J. J. R. Peisen Zhang, Xiaolu Ye and S. G. Fischer, Integrated
mapping package, Genomics, 55 (1999), pp. 78–87.
[10] D. B. West, Introduction to Graph Theory, Prentice Hall, 2001.
33
此全文未授權公開