1. NCCU Academic Hub
  2. 學術產出
  3. College of Science
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

  • No doi shows Citation Infomation
題名 完全C邊混合超圖的著色多項式
The Chromatic Polynomial of A Mixed Hypergraph with Complete C-edges
作者 吳仕傑
貢獻者 張宜武
吳仕傑
關鍵詞 混合超圖
分離-收縮法
循環的
mixed hypergraph
splitting-contraction algorithm
circular
日期 2007
上傳時間 17-Sep-2009 13:48:14 (UTC+8)
摘要 在這篇論文中，我們利用分離－收縮法(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.
參考文獻 [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.
描述 碩士
國立政治大學
應用數學研究所
94751011
96
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0094751011
資料類型 thesis
dc.contributor.advisor 張宜武zh_TW
dc.contributor.author (Authors) 吳仕傑zh_TW
dc.creator (作者) 吳仕傑zh_TW
dc.date (日期) 2007en_US
dc.date.accessioned 17-Sep-2009 13:48:14 (UTC+8)-
dc.date.available 17-Sep-2009 13:48:14 (UTC+8)-
dc.date.issued (上傳時間) 17-Sep-2009 13:48:14 (UTC+8)-
dc.identifier (Other Identifiers) G0094751011en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/32588-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 應用數學研究所zh_TW
dc.description (描述) 94751011zh_TW
dc.description (描述) 96zh_TW
dc.description.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邊的超圖。		zh_TW
dc.description.abstract (摘要) 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.		en_US
dc.description.tableofcontents Abstract.............................................i
中文摘要.............................................ii
1 Introduction.......................................1
2 Some Obvious Cases.................................4
2.1 Find P(H^(n)_4,λ)..............................5
3 The Relations of P(H^(n)_5,λ).....................14
3.1 Find P(H^(n)_5,λ).............................14
3.2 Find P(H^(n)_k,λ).............................15
4 Solving Π^(k)_n for λ^(k).........................17
4.1 Solutions for Π^(k)_n.........................17
4.2 Future Study..................................21
References..........................................22		zh_TW
dc.format.extent 84856 bytes-
dc.format.extent 142453 bytes-
dc.format.extent 33269 bytes-
dc.format.extent 50812 bytes-
dc.format.extent 83304 bytes-
dc.format.extent 49253 bytes-
dc.format.extent 61730 bytes-
dc.format.extent 25737 bytes-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0094751011en_US
dc.subject (關鍵詞) 混合超圖zh_TW
dc.subject (關鍵詞) 分離-收縮法zh_TW
dc.subject (關鍵詞) 循環的zh_TW
dc.subject (關鍵詞) mixed hypergraphen_US
dc.subject (關鍵詞) splitting-contraction algorithmen_US
dc.subject (關鍵詞) circularen_US
dc.title (題名) 完全C邊混合超圖的著色多項式zh_TW
dc.title (題名) The Chromatic Polynomial of A Mixed Hypergraph with Complete C-edgesen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] Voloshin, V. (1993), The mixed hypergraphs, Comput. Sci. J. Moldova, 1, pp. 45-52.zh_TW
dc.relation.reference (參考文獻) [2] Voloshin, V. and Voss, H.-J. (2000), Circular Mixed hypergraphs I: colorability and unique colorability, Congr. Numer., 144, pp. 207-219.zh_TW
dc.relation.reference (參考文獻) [3] Voloshin, V. (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, American Mathematical Society.zh_TW
dc.relation.reference (參考文獻) [4] West, D.B. (2001), Introduction to Graph Theory, 2nd ed., Prentice Hall.zh_TW