Please use this identifier to cite or link to this item:
https://ah.lib.nccu.edu.tw/handle/140.119/56879| 題名: | 有關有弦探測圖形的探討 Some Problems on Chordal Probe Graphs |
作者: | 李則旻 Lee, Tse Min |
貢獻者: | 張宜武 李則旻 Lee, Tse Min |
關鍵詞: | 有弦圖形 有弦深測圖形 Chordal Graphs Chordal Probe Graphs |
日期: | 2012 | 上傳時間: | 1-Feb-2013 | 摘要: | 在這篇論文中，我們探討有弦探測圖形與三方星狀圖、完美有序圖、\r\n排列圖的關係。另外我們給一些有弦探測圖形的例子並找到一個有弦\r\n探測圖形的必要的條件。最後我們探討一些有關有弦探測圖與其他圖\r\n的包含關係。 1 Introduction 1\r\n2 Some definitions and examples of graphs 4\r\n2.1 Interval graphs and Interval probe graphs . . . . . . . . . . . . . . 4\r\n2.2 Chordal graphs, Chordal probe graphs, and Weakly chordal graphs 6\r\n2.3 Asteroidal triple graphs (AT graphs) . . . . . . . . . . . . . . . . . 7\r\n2.4 Transitive orientations and Comparability graphs . . . . . . . . . . 7\r\n2.5 Alternately orientable graphs . . . . . . . . . . . . . . . . . . . . . 8\r\n2.6 Perfectly orderable graphs . . . . . . . . . . . . . . . . . . . . . . . 9\r\n2.7 Permutation graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 9\r\n2.8 Perfect graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10\r\n2.9 2+2+2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11\r\n3 Chordal probe graphs and other classes of graphs 12\r\n3.1 Chordal probe graphs and asteroidal triple graphs . . . . . . . . . . 12\r\n3.2 Chordal probe graphs and perfectly orderable graphs . . . . . . . . 16\r\n3.3 Chordal probe graphs and permutation graphs . . . . . . . . . . . . 20\r\n3.4 Some examples of chordal probe graphs and a necessary condition of\r\nbeing a chordal probe graph . . . . . . . . . . . . . . . . . . . . . 24\r\n4 Other classes of graphs containing the class of chordal probe graphs 28\r\n4.1 Hierarchy of classes of chordal probe graphs . . . . . . . . . . . . . 28\r\n4.2 Some containment relationships between chordal probe graphs and\r\nother classes of graphs . . . . . . . . . . . . . . . . . . . . . . . . . 29\r\n5 Open Problems and Further Directions of Studies 32\r\nBibliography 33 |
參考文獻: | [1] J. P. S. Andreas Brandstädt, Van Bang Le, Graph classes: A survey,\r\nSIAM Monographs on Discrete Math. and Applications, (1999).\r\n[2] C. Berge and e. Chvatal, Topics on perfect graphs, Annals of discrete\r\nmathematics, 21 (1984).\r\n[3] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic\r\nPress, 1980.\r\n[4] R. B. Hayward, Weakly triangulated graphs, Journal of Combinatorial Theory,\r\nSeries B, 39 (1985), pp. 200–208.\r\n[5] C. G. Lekkerkerker and J. C. Boland, Representation of a finite graph\r\nby a set of intervals on the real line, Fundamenta Mathematicae, 51 (1962),\r\npp. 45–64.\r\n[6] L. L. M. Grotschel and A. Schrijver, The ellipsoid method and its consequences\r\nin combinatorial optimization, Combinatorica, 1 (1981), pp. 169–197.\r\n[7] A. N. T. Martin Charles Golumbic, Tolerance Graphs, Cambridge University\r\nPress, 2004.\r\n[8] M. L. Martin Charles Golumbic, Chordal probe graphs, Discrete Applied\r\nMathematics, 143 (2004), pp. 221–237.\r\n[9] L. L. J. J. R. Peisen Zhang, Xiaolu Ye and S. G. Fischer, Integrated\r\nmapping package, Genomics, 55 (1999), pp. 78–87.\r\n[10] D. B. West, Introduction to Graph Theory, Prentice Hall, 2001.\r\n33 | 描述: | 碩士 國立政治大學 應用數學研究所 99751001 101 |
資料來源: | http://thesis.lib.nccu.edu.tw/record/#G0099751001 | 資料類型: | thesis |
| Appears in Collections: | 學位論文 |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| index.html | 115 B | HTML2 | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.