(3.80.6.131) 您好!臺灣時間:2021/05/14 02:49
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:賴育仁
研究生(外文):Yu-Ren Lai
論文名稱:有關有弦探測圖形的探討
論文名稱(外文):Some Problems on Chordal Probe Graphs
指導教授:林英仁
指導教授(外文):In-Jen Lin
學位類別:碩士
校院名稱:國立臺灣海洋大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2010
畢業學年度:98
語文別:英文
論文頁數:76
中文關鍵詞:有弦探測圖
外文關鍵詞:chordal probe graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:103
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
在這篇論文中我們研究關於「有弦探測圖形」(chordal probe graphs)與「交替有向圖」(alternately orientable graphs),「弱有弦圖形」(weakly chordal graphs),「完美有序圖」(perfect orderable graphs), 「排列圖形」(permutation graphs)和 「嚴格容錯圖形」(proper tolence graphs)之間的關係.我們證明了G是「有弦探測圖形」(chordal probe graphs),那麼G就會是「交替有向圖」(alternately orientable graphs)。我們也討論了G是「不存在三方星狀圖」(AT-fee graphs)但不為「不存在比較性圖形」(cocomparabity graphs),那麼G若且為若包含4種家族圖形,且其中有3種家族圖形補圖為「交替有向圖」(alternately orientable graphs) and 「不存在嚴格容錯圖形」(co-perfect orderable graphs)。我們證明G是「不存在三方星狀圖」(AT-free),但不為「梯形圖」(trapezoid graphs),若G不包含圖3.6,那麼G是「梯形圖」(trapezoid graphs)。我們證明G是「有弦探測圖形」(chordal probe graphs)和「不存在比較性圖形」(cocomparabity graphs),那麼G是「梯形圖」(trapezoid graphs)。我們也證明G和 同時是「有弦圖形」(chordal graphs),G不為「比較性圖形」(comparability graphs)且不為「不存在比較性圖形」(cocomparabity graphs),那麼G, 若且為若包含圖3.9。並且我們研究G是「不存在比較性圖形」(cocomparabitly graphs)且為「容錯圖形」(tolenrance graphs)是否為「有界容錯圖形」(bouned tolenrance graphs)最後我們舉了一些家族在「有弦探測圖形」(chordal probe graphs), 「弱有弦圖形」(weakly chordal graphs),and「完美有序圖」(perfect orderable graphs)。
1 Introduction
1.1 Interval Graphs
1.2 Tolerance graph and Bounded tolerance graph
1.3 Unit tolerance graph and Proper tolerance graph
1.4 Chordal graph and Weakly chordal graph
1.5 Comparability graph and Transitive Orientations
1.6 Asteroidal triple graph
1.7 The Hierarchy of Permutation, Parallelogram, Trapezoid, Function and AT-free Graph
1.8 Alternately orientable graph
1.9 Perfectly orderable graph
1.10 The Perfect Graph Theorem
1.11 Dimension and Interval Dimension
2 Some problem of Chordal probe graphs
2.1 Chordal probe graphs
2.2 Relation of Chordal probe graphs and Alternately orientable graphs
2.3 The relation among chordal probe, weakly chordal, perfect orderable, permutation
graphs and proper tolence graphs
3 Relation of AT-free and Cocomparability
3.1 Relation of AT-free and cocomparability graphs
3.2 Relation of cocomparabitly graph and tolerance graph
4 Conclusions and Furture Work
[1] M.C. Golumbic. Algorithmic Graph Theory and Perfect Graphs.
Academic Press, San Diego, CA, 1980.
[2] R.B. Hayward. Weakly triangulated graphs. J. of Comb. Theory
B., 39:200-209, 1985.
[3] A. Pnueli, A. Lempel, and S. Even. Transitive orientation of
graphs and identification of permutation graphs. Canad. J. Math.,
23:160-175, 1971.
[4] V.Chvatal.Perectly order graphs.McGill Univ.Report SOCS
81.28,1981
[5] C. Berge and V. Chv’atal, editors. Topics on Perfect Graphs, volume
21 of Ann. Discrete Math. North-Holland, Amsterdam, 1984.
[6] A. Brandstadt, V.B. Le, and J.P. Spinrad. Graph Classes: A
Survey. SIAM Monographs on Discrete Math. and Applications,
Philadelphia, 1999.
[7] M. GrLotschel, L. Lov’asz, and A. Schrijver. The elipsoid
method and its consequences in combinatorial optimization.
Combinatorica, 1:169-197, 1981.
[8] L. Lov’asz. A characterization of perfect graphs. J. Combin. Theory
B, 13:95-98, 1972.
[9] Mc Golumbic,QAN Trenk.Tolerance graphs-Cambridge University
Press,2004
[10] D. Mackenzie. Graph theory uncovers the roots of perfection. Science,
297:38, July 5 2002.
[11] M.C. Golumbic, C.L. Monma, and W.T. Trotter. Tolerance
graphs. Discrete Applied Math., 9:157-170, 1984.
[12] P. Zhang. Probe interval graphs and their application to physical
mapping of DNA. Manuscript, 1994.
[13] P. Zhang, E.A. Schon, S.G. Fischer, E. Cayanis, J. Weiss, S.
Kistler, and P.E. Bourne. An algorithm based on graph theory
for the assembly of contigs in physical mapping of DNA.
[14] P. Zhang, X. Ye, L. Liao, J. Russo, and S.G. Fischer. Integrated
mapping package - a physical mapping software tool kit. Genomics,
55:78-87, 1999.
[15] M.c Golumbic and Marina Lipshteyn.Chordal Probe
Graphsextendedabstravt
[16] M.c Golumbic, A.N.Trenk,Tolerance Graphs,Cambridge University
Press(2003)
[17] I,J.Lin, JH.Chen.Relation of Chordal probe Graphs and Torance
Graphs, 2005
[18] M.C. Golumbic, D. Rotem, and J. Urrutia. Comparability graphs
and intersection graphs. Discrete Math., 43:37-46, 1983.
[19] I,J.Lin, C.H.Wu.Some Problem on Interval Probe graphs and Perfect
Graphs.2009
[20] S. Felsner. Tolerance graphs and orders. J. of Graph Theory,
28:129-140, 1998.
[21] Vorgelegt von Dipl-Math.Ekkehard G.kohler. Graphs without asteroidal
t riples.9.Juli 1999.
[22] Celina M. H. de Figueiredo Joao Meidanis Celina Picinin de Mello
A greedy method for edge-clolouring odd maximum degree doubly
chordal graphs.Junho de 1995
[23] Martin Charles Golumbic Ann N.Trenk. Tolerance
Graphs.December 6,2002.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔