1. NCCU Academic Hub
  2. 理學院
  3. 應用數學系
  4. 學位論文
Please use this identifier to cite or link to this item: https://ah.lib.nccu.edu.tw/handle/140.119/56879
DC FieldValueLanguage
dc.contributor.advisor張宜武zh_TW
dc.contributor.author李則旻zh_TW
dc.contributor.authorLee, Tse Minen_US
dc.creator李則旻zh_TW
dc.creatorLee, Tse Minen_US
dc.date2012en_US
dc.date.accessioned2013-02-01T08:53:17Z-
dc.date.available2013-02-01T08:53:17Z-
dc.date.issued2013-02-01T08:53:17Z-
dc.identifierG0099751001en_US
dc.identifier.urihttp://nccur.lib.nccu.edu.tw/handle/140.119/56879-
dc.description碩士zh_TW
dc.description國立政治大學zh_TW
dc.description應用數學研究所zh_TW
dc.description99751001zh_TW
dc.description101zh_TW
dc.description.abstract在這篇論文中，我們探討有弦探測圖形與三方星狀圖、完美有序圖、\r\n排列圖的關係。另外我們給一些有弦探測圖形的例子並找到一個有弦\r\n探測圖形的必要的條件。最後我們探討一些有關有弦探測圖與其他圖\r\n的包含關係。zh_TW
dc.description.abstract1 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-
dc.description.tableofcontents1 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 33zh_TW
dc.language.isoen_US-
dc.source.urihttp://thesis.lib.nccu.edu.tw/record/#G0099751001en_US
dc.subject有弦圖形zh_TW
dc.subject有弦深測圖形zh_TW
dc.subjectChordal Graphsen_US
dc.subjectChordal Probe Graphsen_US
dc.title有關有弦探測圖形的探討zh_TW
dc.titleSome Problems on Chordal Probe Graphsen_US
dc.typethesisen
dc.relation.reference[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\n33zh_TW
item.fulltextWith Fulltext-
item.openairetypethesis-
item.grantfulltextopen-
item.cerifentitytypePublications-
item.openairecristypehttp://purl.org/coar/resource_type/c_46ec-
item.languageiso639-1en_US-
Appears in Collections:學位論文
Files in This Item:
File SizeFormat
index.html115 BHTML2View/Open
Show simple item record

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.