English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 90533/120562 (75%)
Visitors : 24974409      Online Users : 290
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    政大機構典藏 > 理學院 > 應用數學系 > 學位論文 >  Item 140.119/32588
    Please use this identifier to cite or link to this item: http://nccur.lib.nccu.edu.tw/handle/140.119/32588


    Title: 完全C邊混合超圖的著色多項式
    The Chromatic Polynomial of A Mixed Hypergraph with Complete C-edges
    Authors: 吳仕傑
    Contributors: 張宜武
    吳仕傑
    Keywords: 混合超圖
    分離-收縮法
    循環的
    mixed hypergraph
    splitting-contraction algorithm
    circular
    Date: 2007
    Issue Date: 2009-09-17 13:48:14 (UTC+8)
    Abstract: 在這篇論文中,我們利用分離-收縮法(splitting-contraction algorithm)獲得一個擁有完全C邊以及循環D邊特性的圖之著色多項式。 假如一個混合超圖在點集合上有主要的循環, 使得所有的C邊和D邊包含一個主循環(host cycle)的連接子圖, 則稱此圖為循環的(circular)。 對於每個l≧2, 所有連續l個點會形成一個D邊時, 我們把D記作D_l。 如此一來, 超圖(X,Φ,D_2)就是圖論中n個點的普通循環。
    我們先觀察擁有完全C邊和循環D邊的超圖, 利用分離-收縮法的第一步, 找到遞迴關係式並且解它。 然後我們就推廣到一般完全C邊及循環D邊的超圖。
    In this thesis, we obtain the chromatic polynomial of a mixed hypergraph with complete C-edges and circular D-edges by using splitting-contraction algorithm. A mixed hypergraph H=(X,C,D) is called circular if there exists a host cycle on the vertex set X such that every C-edge and every D-edge induces a connected subgraph of the host cycle. For each l≧2, we denote D by D_l if and only if every l consecutive vertices of X form a D-edge. Thus the mixed hypergraph (X,Φ,D_2) is a simple classical cycle on n vertices.
    We observe first a mixed hypergraph with complete C-edges and D_2. By the first step of the splitting-contraction algorithm, we can find out the recurrence relation and solve it. Then we generalize the mixed hypergraph with complete C-edges and circular D-edges.
    Reference: [1] Voloshin, V. (1993), The mixed hypergraphs, Comput. Sci. J. Moldova, 1, pp. 45-52.
    [2] Voloshin, V. and Voss, H.-J. (2000), Circular Mixed hypergraphs I: colorability and unique colorability, Congr. Numer., 144, pp. 207-219.
    [3] Voloshin, V. (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, American Mathematical Society.
    [4] West, D.B. (2001), Introduction to Graph Theory, 2nd ed., Prentice Hall.
    Description: 碩士
    國立政治大學
    應用數學研究所
    94751011
    96
    Source URI: http://thesis.lib.nccu.edu.tw/record/#G0094751011
    Data Type: thesis
    Appears in Collections:[應用數學系] 學位論文

    Files in This Item:

    File Description SizeFormat
    101101.pdf82KbAdobe PDF887View/Open
    101102.pdf139KbAdobe PDF785View/Open
    101103.pdf32KbAdobe PDF611View/Open
    101104.pdf49KbAdobe PDF678View/Open
    101105.pdf81KbAdobe PDF737View/Open
    101106.pdf48KbAdobe PDF670View/Open
    101107.pdf60KbAdobe PDF640View/Open
    101108.pdf25KbAdobe PDF622View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告
    1.本網站之數位內容為國立政治大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,惟仍請適度,合理使用本網站之內容,以尊重著作權人之權益。商業上之利用,則請先取得著作權人之授權。
    2.本網站之製作,已盡力防止侵害著作權人之權益,如仍發現本網站之數位內容有侵害著作權人權益情事者,請權利人通知本網站維護人員(nccur@nccu.edu.tw),維護人員將立即採取移除該數位著作等補救措施。
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback