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

Title最大，二分，外平面圖之容忍表示法
The Tolerance Representations of Maximal Bipartite Outerplanar Graphs
Creator賴昱儒
Contributor張宜武
賴昱儒
Key Words最大外平面圖
二分圖
容忍表示法
Tolerance Graphs
Maximal Outerplanar Graphs
Bipartite
Date2009
Date Issued8-Dec-2010 11:54:45 (UTC+8)
Summary在這篇論文中，我們針對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.
Description碩士
國立政治大學
應用數學研究所
96751006
98
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0967510061
Typethesis
dc.contributor.advisor 張宜武zh_TW
dc.contributor.author (Authors) 賴昱儒zh_TW
dc.creator (作者) 賴昱儒zh_TW
dc.date (日期) 2009en_US
dc.date.accessioned 8-Dec-2010 11:54:45 (UTC+8)-
dc.date.available 8-Dec-2010 11:54:45 (UTC+8)-
dc.date.issued (上傳時間) 8-Dec-2010 11:54:45 (UTC+8)-
dc.identifier (Other Identifiers) G0967510061en_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 (描述) 96751006zh_TW
dc.description (描述) 98zh_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/#G0967510061en_US
dc.subject (關鍵詞) 最大外平面圖zh_TW
dc.subject (關鍵詞) 二分圖zh_TW
dc.subject (關鍵詞) 容忍表示法zh_TW
dc.subject (關鍵詞) Tolerance Graphsen_US
dc.subject (關鍵詞) Maximal Outerplanar Graphsen_US
dc.subject (關鍵詞) Bipartiteen_US
dc.title (題名) 最大，二分，外平面圖之容忍表示法zh_TW
dc.title (題名) The Tolerance Representations of Maximal Bipartite Outerplanar Graphsen_US
dc.type (資料類型) thesisen
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