| dc.contributor.advisor | 張宜武 | zh_TW |
| dc.contributor.author (Authors) | 郭瓊雲 | zh_TW |
| dc.creator (作者) | 郭瓊雲 | zh_TW |
| dc.date (日期) | 2008 | en_US |
| dc.date.accessioned | 9-May-2016 11:58:27 (UTC+8) | - |
| dc.date.available | 9-May-2016 11:58:27 (UTC+8) | - |
| dc.date.issued (上傳時間) | 9-May-2016 11:58:27 (UTC+8) | - |
| dc.identifier (Other Identifiers) | G0095751006 | en_US |
| dc.identifier.uri (URI) | https://ah.lib.nccu.edu.tw/item?item_id=106983 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 應用數學系 | zh_TW |
| dc.description (描述) | 95751006 | zh_TW |
| dc.description.abstract (摘要) | 本文針對2-連通的最大外平面圖，討論其有界容忍表示法，且找到禁止子圖S3。我們更進一步證明：如果一個2-連通的最大外平面圖恰有兩個點的度為2時，則此圖為區間圖。 | zh_TW |
| dc.description.abstract (摘要) | We prove that a 2-connected maximal outerplanar graph G is a bounded tolerance graph if and only if there is no induced subgraph S3 of G and G has no\r\ninduced subgraph S3 if and only if G is an interval graph. | en_US |
| dc.description.abstract (摘要) | Contents\r\nAbstract i\r\n中文摘要 ii\r\n1 Introduction 1\r\n1.1 History of tolerance graphs ...........................1\r\n1.2 The structure of tolerance graphs......................3\r\n2 Tolerance graphs 4\r\n2.1 Definition and theorems of tolerance graphs............4\r\n2.2 Bounded tolerance representations for trees and bipartite graphs ..........................................8\r\n3 Some results on maximal outerplanar graphs 10\r\n3.1 A 2-connected maximal outerplanar graph is not necessarily a tolerance graph.............................10\r\n3.2 Bounded tolerance representations for 2-connected maximal outerplanar graphs................................15\r\n4 Open problems and further directions of study 22\r\nReferences 23 | - |
| dc.description.tableofcontents | Contents\r\nAbstract i\r\n中文摘要 ii\r\n1 Introduction 1\r\n1.1 History of tolerance graphs ...........................1\r\n1.2 The structure of tolerance graphs......................3\r\n2 Tolerance graphs 4\r\n2.1 Definition and theorems of tolerance graphs............4\r\n2.2 Bounded tolerance representations for trees and bipartite graphs ..........................................8\r\n3 Some results on maximal outerplanar graphs 10\r\n3.1 A 2-connected maximal outerplanar graph is not necessarily a tolerance graph.............................10\r\n3.2 Bounded tolerance representations for 2-connected maximal outerplanar graphs................................15\r\n4 Open problems and further directions of study 22\r\nReferences 23 | zh_TW |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0095751006 | en_US |
| dc.subject (關鍵詞) | 最大外平面圖 | zh_TW |
| dc.subject (關鍵詞) | 有界容忍表示法 | zh_TW |
| dc.subject (關鍵詞) | 區間圖 | zh_TW |
| dc.subject (關鍵詞) | Tolerance graphs | en_US |
| dc.subject (關鍵詞) | Maximal outerplanar graphs | en_US |
| dc.subject (關鍵詞) | Interval graphs | en_US |
| dc.title (題名) | 最大外平面圖的有界容忍表示法 | zh_TW |
| dc.title (題名) | Bounded Tolerance Representation for Maximal Outerplanar Graphs | en_US |
| dc.type (資料類型) | thesis | en_US |
| dc.relation.reference (參考文獻) | [1] K. Bogart, P. Fishburn, G. Isaak, and L. Langley, 1995. Proper and unit tolerance\r\ngraphs. Discrete Applied Math., 60 37-51.\r\n[2] S. Felsner, 1998. Tolerance graphs and orders. J. Graph Theory, 28 129{140.\r\n[3] S. Fisher, R. MÄuller, and L. Wernisch, 1997. Trapezoid graphs and generaliza-\r\ntions, geometry and algorithms. Discrete Applied Math., 74 13-32.\r\n[4] M. C. Golumbic, 1980. Algorithmic Graph Theory and Perfect graphs. Academic\r\nPress.\r\n[5] M. C. Golumbic and C. L. Monma, 1982. A generalization of interval graphs\r\nwith tolerances. Congress. Numer., 15 321-331.\r\n[6] M. C. Golumbic, C. L. Monma, and W. T. Trotter, 1984. Tolerance graphs.\r\nDiscrete Applied Math., 9 157-170.\r\n[7] M. C. Golumbic and A. N. Trenk, 2004. Tolerance graphs, Cambridge University\r\nPress. Cambridge.\r\n[8] M. C. Golumbic, D. Rotem, and J. Urrutia, 1983. Comparability graphs and\r\nintersection graphs. Discrete Math., 43 37-46.\r\n[9] R. B. Hayward and R. Shamir, 2002. A note on tolerance graph recognition.\r\nDiscrete Applied Math.\r\n[10] M. S. Jacobsen, F. R. McMorris and E. R. Scheinerman, General results on\r\ntolerance intersection graphs. J. Graph Theory, 15 573-578.\r\n[11] L. Langley, 1993. Interval tolerance orders and dimension. Ph. D. thesis, Dart-\r\nmouth College. | zh_TW |
