Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/56879
|
| Title: | 有關有弦探測圖形的探討
Some Problems on Chordal Probe Graphs |
| Authors: | 李則旻
Lee, Tse Min |
| Contributors: | 張宜武
李則旻
Lee, Tse Min |
| Keywords: | 有弦圖形
有弦深測圖形
Chordal Graphs
Chordal Probe Graphs |
| Date: | 2012 |
| Issue Date: | 2013-02-01 16:53:17 (UTC+8) |
| Abstract: | 在這篇論文中，我們探討有弦探測圖形與三方星狀圖、完美有序圖、
排列圖的關係。另外我們給一些有弦探測圖形的例子並找到一個有弦
探測圖形的必要的條件。最後我們探討一些有關有弦探測圖與其他圖
的包含關係。
1 Introduction 1
2 Some definitions and examples of graphs 4
2.1 Interval graphs and Interval probe graphs . . . . . . . . . . . . . . 4
2.2 Chordal graphs, Chordal probe graphs, and Weakly chordal graphs 6
2.3 Asteroidal triple graphs (AT graphs) . . . . . . . . . . . . . . . . . 7
2.4 Transitive orientations and Comparability graphs . . . . . . . . . . 7
2.5 Alternately orientable graphs . . . . . . . . . . . . . . . . . . . . . 8
2.6 Perfectly orderable graphs . . . . . . . . . . . . . . . . . . . . . . . 9
2.7 Permutation graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.8 Perfect graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.9 2+2+2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Chordal probe graphs and other classes of graphs 12
3.1 Chordal probe graphs and asteroidal triple graphs . . . . . . . . . . 12
3.2 Chordal probe graphs and perfectly orderable graphs . . . . . . . . 16
3.3 Chordal probe graphs and permutation graphs . . . . . . . . . . . . 20
3.4 Some examples of chordal probe graphs and a necessary condition of
being a chordal probe graph . . . . . . . . . . . . . . . . . . . . . 24
4 Other classes of graphs containing the class of chordal probe graphs 28
4.1 Hierarchy of classes of chordal probe graphs . . . . . . . . . . . . . 28
4.2 Some containment relationships between chordal probe graphs and
other classes of graphs . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Open Problems and Further Directions of Studies 32
Bibliography 33 |
| Reference: | [1] J. P. S. Andreas Brandstädt, Van Bang Le, Graph classes: A survey,
SIAM Monographs on Discrete Math. and Applications, (1999).
[2] C. Berge and e. Chvatal, Topics on perfect graphs, Annals of discrete
mathematics, 21 (1984).
[3] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic
Press, 1980.
[4] R. B. Hayward, Weakly triangulated graphs, Journal of Combinatorial Theory,
Series B, 39 (1985), pp. 200–208.
[5] C. G. Lekkerkerker and J. C. Boland, Representation of a finite graph
by a set of intervals on the real line, Fundamenta Mathematicae, 51 (1962),
pp. 45–64.
[6] L. L. M. Grotschel and A. Schrijver, The ellipsoid method and its consequences
in combinatorial optimization, Combinatorica, 1 (1981), pp. 169–197.
[7] A. N. T. Martin Charles Golumbic, Tolerance Graphs, Cambridge University
Press, 2004.
[8] M. L. Martin Charles Golumbic, Chordal probe graphs, Discrete Applied
Mathematics, 143 (2004), pp. 221–237.
[9] L. L. J. J. R. Peisen Zhang, Xiaolu Ye and S. G. Fischer, Integrated
mapping package, Genomics, 55 (1999), pp. 78–87.
[10] D. B. West, Introduction to Graph Theory, Prentice Hall, 2001.
33 |
| Description: | 碩士
國立政治大學
應用數學研究所
99751001
101 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0099751001 |
| Data Type: | thesis |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| index.html | 0Kb | HTML2 | 435 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
