1. NCCU Academic Hub
  2. Publications
  3. College of Science
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 有關有弦探測圖形的探討
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 Minen_US
dc.creator (作者) 李則旻zh_TW
dc.creator (作者) Lee, Tse Minen_US
dc.date (日期) 2012en_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) G0099751001en_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 (描述) 99751001zh_TW
dc.description (描述) 101zh_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/#G0099751001en_US
dc.subject (關鍵詞) 有弦圖形zh_TW
dc.subject (關鍵詞) 有弦深測圖形zh_TW
dc.subject (關鍵詞) Chordal Graphsen_US
dc.subject (關鍵詞) Chordal Probe Graphsen_US
dc.title (題名) 有關有弦探測圖形的探討zh_TW
dc.title (題名) Some Problems on Chordal Probe Graphsen_US
dc.type (資料類型) thesisen
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