(3.80.6.131) 您好！臺灣時間：2021/05/14 02:49

### 詳目顯示:::

:

• 被引用: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 Introduction1.1 Interval Graphs1.2 Tolerance graph and Bounded tolerance graph1.3 Unit tolerance graph and Proper tolerance graph1.4 Chordal graph and Weakly chordal graph1.5 Comparability graph and Transitive Orientations1.6 Asteroidal triple graph1.7 The Hierarchy of Permutation, Parallelogram, Trapezoid, Function and AT-free Graph1.8 Alternately orientable graph1.9 Perfectly orderable graph1.10 The Perfect Graph Theorem1.11 Dimension and Interval Dimension2 Some problem of Chordal probe graphs2.1 Chordal probe graphs2.2 Relation of Chordal probe graphs and Alternately orientable graphs2.3 The relation among chordal probe, weakly chordal, perfect orderable, permutationgraphs and proper tolence graphs3 Relation of AT-free and Cocomparability3.1 Relation of AT-free and cocomparability graphs3.2 Relation of cocomparabitly graph and tolerance graph4 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. TheoryB., 39:200-209, 1985.[3] A. Pnueli, A. Lempel, and S. Even. Transitive orientation ofgraphs and identification of permutation graphs. Canad. J. Math.,23:160-175, 1971.[4] V.Chvatal.Perectly order graphs.McGill Univ.Report SOCS81.28,1981[5] C. Berge and V. Chv’atal, editors. Topics on Perfect Graphs, volume21 of Ann. Discrete Math. North-Holland, Amsterdam, 1984.[6] A. Brandstadt, V.B. Le, and J.P. Spinrad. Graph Classes: ASurvey. SIAM Monographs on Discrete Math. and Applications,Philadelphia, 1999.[7] M. GrLotschel, L. Lov’asz, and A. Schrijver. The elipsoidmethod and its consequences in combinatorial optimization.Combinatorica, 1:169-197, 1981.[8] L. Lov’asz. A characterization of perfect graphs. J. Combin. TheoryB, 13:95-98, 1972.[9] Mc Golumbic,QAN Trenk.Tolerance graphs-Cambridge UniversityPress,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. Tolerancegraphs. Discrete Applied Math., 9:157-170, 1984.[12] P. Zhang. Probe interval graphs and their application to physicalmapping 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 theoryfor the assembly of contigs in physical mapping of DNA.[14] P. Zhang, X. Ye, L. Liao, J. Russo, and S.G. Fischer. Integratedmapping package - a physical mapping software tool kit. Genomics,55:78-87, 1999.[15] M.c Golumbic and Marina Lipshteyn.Chordal ProbeGraphsextendedabstravt[16] M.c Golumbic, A.N.Trenk,Tolerance Graphs,Cambridge UniversityPress(2003)[17] I,J.Lin, JH.Chen.Relation of Chordal probe Graphs and ToranceGraphs, 2005[18] M.C. Golumbic, D. Rotem, and J. Urrutia. Comparability graphsand intersection graphs. Discrete Math., 43:37-46, 1983.[19] I,J.Lin, C.H.Wu.Some Problem on Interval Probe graphs and PerfectGraphs.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 asteroidalt riples.9.Juli 1999.[22] Celina M. H. de Figueiredo Joao Meidanis Celina Picinin de MelloA greedy method for edge-clolouring odd maximum degree doublychordal graphs.Junho de 1995[23] Martin Charles Golumbic Ann N.Trenk. ToleranceGraphs.December 6,2002.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 樹的對立圖形及有關排列圖形的探討 2 鄰居子樹圖裡的門檻圖結構 3 路徑長度為四-比較性圖形及其相關問題的討論 4 連通p-重心問題演算法之研究 5 基於數位相片內容的影像色彩修正技術 6 K-regular graphs edges connectivity and related topics 7 「可視秘密碎片」馬賽克畫—一種新的藝術與其在資 訊隱藏上的應用 8 硬幣移動問題的計算複雜度 9 校園行動裝置門禁管理系統之研究 10 標記支配及其相關問題 11 強弦圖上的容錯支配問題 12 青少年對寶特瓶造形認知研究 13 市區中路邊輔助裝置之布局 14 有關單位格網交集圖形及相關問題的探討 15 Torus圖形之符號支配數的研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室