學術產出-Theses
Article View/Open
Publication Export
-
題名 有關有弦探測圖形的探討
Some Problems on Chordal Probe Graphs作者 李則旻
Lee, Tse Min貢獻者 張宜武
李則旻
Lee, Tse Min關鍵詞 有弦圖形
有弦深測圖形
Chordal Graphs
Chordal Probe Graphs日期 2012 上傳時間 1-Feb-2013 16:53:17 (UTC+8) 摘要 在這篇論文中,我們探討有弦探測圖形與三方星狀圖、完美有序圖、 排列圖的關係。另外我們給一些有弦探測圖形的例子並找到一個有弦 探測圖形的必要的條件。最後我們探討一些有關有弦探測圖與其他圖 的包含關係。
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 描述 碩士
國立政治大學
應用數學研究所
99751001
101資料來源 http://thesis.lib.nccu.edu.tw/record/#G0099751001 資料類型 thesis dc.contributor.advisor 張宜武 zh_TW dc.contributor.author (Authors) 李則旻 zh_TW dc.contributor.author (Authors) Lee, Tse Min en_US dc.creator (作者) 李則旻 zh_TW dc.creator (作者) Lee, Tse Min en_US dc.date (日期) 2012 en_US dc.date.accessioned 1-Feb-2013 16:53:17 (UTC+8) - dc.date.available 1-Feb-2013 16:53:17 (UTC+8) - dc.date.issued (上傳時間) 1-Feb-2013 16:53:17 (UTC+8) - dc.identifier (Other Identifiers) G0099751001 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/56879 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學研究所 zh_TW dc.description (描述) 99751001 zh_TW dc.description (描述) 101 zh_TW dc.description.abstract (摘要) 在這篇論文中,我們探討有弦探測圖形與三方星狀圖、完美有序圖、 排列圖的關係。另外我們給一些有弦探測圖形的例子並找到一個有弦 探測圖形的必要的條件。最後我們探討一些有關有弦探測圖與其他圖 的包含關係。 zh_TW dc.description.abstract (摘要) 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 - dc.description.tableofcontents 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 zh_TW dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0099751001 en_US dc.subject (關鍵詞) 有弦圖形 zh_TW dc.subject (關鍵詞) 有弦深測圖形 zh_TW dc.subject (關鍵詞) Chordal Graphs en_US dc.subject (關鍵詞) Chordal Probe Graphs en_US dc.title (題名) 有關有弦探測圖形的探討 zh_TW dc.title (題名) Some Problems on Chordal Probe Graphs en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [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 zh_TW