學術產出-學位論文
| 題名 | 最大，二分，外平面圖之容忍表示法 The Tolerance Representations of Maximal Bipartite Outerplanar Graphs |
| 作者 | 賴昱儒 |
| 貢獻者 | 張宜武 賴昱儒 |
| 關鍵詞 | 最大外平面圖 二分圖 容忍表示法 Tolerance Graphs Maximal Outerplanar Graphs Bipartite |
| 日期 | 2009 |
| 上傳時間 | 8-十二月-2010 11:54:45 (UTC+8) |
| 摘要 | 在這篇論文中，我們針對2-連通的最大外平面圖而且是二分圖的圖形，討論 其容忍表示法，並找到它的所有禁止子圖H1、H2、H3、H4。 In this thesis, we prove a 2-connected graph G which is maximal outerplanar and bipartite is a tolerance graph if and only if there is no induced subgraphs H1; H2; H3 and H4 of G. |
| 參考文獻 | [1] M. Golumbic and C. Monma, A generalization of interval graphs with tolerances, Congressus Numerantium, 35 (1982), pp. 321-331. [2] M. Golumbic, D. Rotem, and J. Urrutia, Comparability graphs and intersection graphs, Discrete Math., 43 (1983), pp. 37-46. [3] M. Golumbic and A. Trenk, Tolerance graphs, Cambridge Univ Pr, 2004. [4] R. Hayward and R. Shamir, A note on tolerance graph recognition, Discrete Applied Mathematics, 143 (2004), pp. 307-311. |
| 描述 | 碩士 國立政治大學 應用數學研究所 96751006 98 |
| 資料來源 | http://thesis.lib.nccu.edu.tw/record/#G0967510061 |
| 資料類型 | thesis |
| dc.contributor.advisor | 張宜武 | zh_TW |
| dc.contributor.author (作者) | 賴昱儒 | zh_TW |
| dc.creator (作者) | 賴昱儒 | zh_TW |
| dc.date (日期) | 2009 | en_US |
| dc.date.accessioned | 8-十二月-2010 11:54:45 (UTC+8) | - |
| dc.date.available | 8-十二月-2010 11:54:45 (UTC+8) | - |
| dc.date.issued (上傳時間) | 8-十二月-2010 11:54:45 (UTC+8) | - |
| dc.identifier (其他 識別碼) | G0967510061 | en_US |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/49463 | - |
| dc.description (描述) | 碩士 | zh_TW |
| dc.description (描述) | 國立政治大學 | zh_TW |
| dc.description (描述) | 應用數學研究所 | zh_TW |
| dc.description (描述) | 96751006 | zh_TW |
| dc.description (描述) | 98 | zh_TW |
| dc.description.abstract (摘要) | 在這篇論文中，我們針對2-連通的最大外平面圖而且是二分圖的圖形，討論 其容忍表示法，並找到它的所有禁止子圖H1、H2、H3、H4。 | zh_TW |
| dc.description.abstract (摘要) | In this thesis, we prove a 2-connected graph G which is maximal outerplanar and bipartite is a tolerance graph if and only if there is no induced subgraphs H1; H2; H3 and H4 of G. | en_US |
| dc.description.tableofcontents | Abstract ii 中文摘要iii 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 Theorem of Tolerance Graph 4 2.2 Bounded Tolerance Representations for Trees and Bipartite Graphs 6 2.3 A Tolerance Representation of C4 7 2.4 A Tolerance Representation of Concatenation of Two 4-cycles 10 2.5 A Tolerance Representation of Concatenation of Three 4-cycles 12 3 Some Results on Maximal Outerplanar Graphs 20 3.1 A 2-connected Graph Which Is Maximal Outerplanar Graph and Bipartite Is Not Necessarily a Tolerance Graph 20 4 Open Problems and Further Directions of Studies 30 References 31 | zh_TW |
| dc.format.extent | 1515087 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.language.iso | en_US | - |
| dc.source.uri (資料來源) | http://thesis.lib.nccu.edu.tw/record/#G0967510061 | 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 (關鍵詞) | Bipartite | en_US |
| dc.title (題名) | 最大，二分，外平面圖之容忍表示法 | zh_TW |
| dc.title (題名) | The Tolerance Representations of Maximal Bipartite Outerplanar Graphs | en_US |
| dc.type (資料類型) | thesis | en |
| dc.relation.reference (參考文獻) | [1] M. Golumbic and C. Monma, A generalization of interval graphs with tolerances, Congressus Numerantium, 35 (1982), pp. 321-331. | zh_TW |
| dc.relation.reference (參考文獻) | [2] M. Golumbic, D. Rotem, and J. Urrutia, Comparability graphs and intersection graphs, Discrete Math., 43 (1983), pp. 37-46. | zh_TW |
| dc.relation.reference (參考文獻) | [3] M. Golumbic and A. Trenk, Tolerance graphs, Cambridge Univ Pr, 2004. | zh_TW |
| dc.relation.reference (參考文獻) | [4] R. Hayward and R. Shamir, A note on tolerance graph recognition, Discrete Applied Mathematics, 143 (2004), pp. 307-311. | zh_TW |