| 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) | http://nccur.lib.nccu.edu.tw/handle/140.119/94850 | - |
| 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 induced subgraph S3 if and only if G is an interval graph. | en_US |
| dc.description.abstract (摘要) | Contents Abstract i 中文摘要 ii 1 Introduction 1 1.1 History of tolerance graphs ...........................1 1.2 The structure of tolerance graphs......................3 2 Tolerance graphs 4 2.1 Definition and theorems of tolerance graphs............4 2.2 Bounded tolerance representations for trees and bipartite graphs ..........................................8 3 Some results on maximal outerplanar graphs 10 3.1 A 2-connected maximal outerplanar graph is not necessarily a tolerance graph.............................10 3.2 Bounded tolerance representations for 2-connected maximal outerplanar graphs................................15 4 Open problems and further directions of study 22 References 23 | - |
| dc.description.tableofcontents | Contents Abstract i 中文摘要 ii 1 Introduction 1 1.1 History of tolerance graphs ...........................1 1.2 The structure of tolerance graphs......................3 2 Tolerance graphs 4 2.1 Definition and theorems of tolerance graphs............4 2.2 Bounded tolerance representations for trees and bipartite graphs ..........................................8 3 Some results on maximal outerplanar graphs 10 3.1 A 2-connected maximal outerplanar graph is not necessarily a tolerance graph.............................10 3.2 Bounded tolerance representations for 2-connected maximal outerplanar graphs................................15 4 Open problems and further directions of study 22 References 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 graphs. Discrete Applied Math., 60 37-51. [2] S. Felsner, 1998. Tolerance graphs and orders. J. Graph Theory, 28 129{140. [3] S. Fisher, R. MÄuller, and L. Wernisch, 1997. Trapezoid graphs and generaliza- tions, geometry and algorithms. Discrete Applied Math., 74 13-32. [4] M. C. Golumbic, 1980. Algorithmic Graph Theory and Perfect graphs. Academic Press. [5] M. C. Golumbic and C. L. Monma, 1982. A generalization of interval graphs with tolerances. Congress. Numer., 15 321-331. [6] M. C. Golumbic, C. L. Monma, and W. T. Trotter, 1984. Tolerance graphs. Discrete Applied Math., 9 157-170. [7] M. C. Golumbic and A. N. Trenk, 2004. Tolerance graphs, Cambridge University Press. Cambridge. [8] M. C. Golumbic, D. Rotem, and J. Urrutia, 1983. Comparability graphs and intersection graphs. Discrete Math., 43 37-46. [9] R. B. Hayward and R. Shamir, 2002. A note on tolerance graph recognition. Discrete Applied Math. [10] M. S. Jacobsen, F. R. McMorris and E. R. Scheinerman, General results on tolerance intersection graphs. J. Graph Theory, 15 573-578. [11] L. Langley, 1993. Interval tolerance orders and dimension. Ph. D. thesis, Dart- mouth College. | zh_TW |
