政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/56879
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文筆數/總筆數 : 114367/145401 (79%)
造訪人次 : 53050767      線上人數 : 651
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧：
  • 您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料
    •  進階搜尋
    政大機構典藏 > 理學院 > 應用數學系 > 學位論文 >  Item 140.119/56879


    請使用永久網址來引用或連結此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/56879


    題名: 有關有弦探測圖形的探討
    Some Problems on Chordal Probe Graphs
    作者: 李則旻
    Lee, Tse Min
    貢獻者: 張宜武
    李則旻
    Lee, Tse Min
    關鍵詞: 有弦圖形
    有弦深測圖形
    Chordal Graphs
    Chordal Probe Graphs
    日期: 2012
    上傳時間: 2013-02-01 16:53:17 (UTC+8)
    摘要: 在這篇論文中，我們探討有弦探測圖形與三方星狀圖、完美有序圖、
    排列圖的關係。另外我們給一些有弦探測圖形的例子並找到一個有弦
    探測圖形的必要的條件。最後我們探討一些有關有弦探測圖與其他圖
    的包含關係。
    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
    參考文獻: [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
    描述: 碩士
    國立政治大學
    應用數學研究所
    99751001
    101
    資料來源: http://thesis.lib.nccu.edu.tw/record/#G0099751001
    資料類型: thesis
    顯示於類別:[應用數學系] 學位論文

    文件中的檔案:

    檔案 大小格式瀏覽次數
    index.html0KbHTML2512檢視/開啟


    在政大典藏中所有的資料項目都受到原著作權保護.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回饋