簡易檢索 / 詳目顯示
| 研究生： |
吳仕傑 |
|---|---|
| 論文名稱： |
完全C邊混合超圖的著色多項式 The Chromatic Polynomial of A Mixed Hypergraph with Complete C-edges |
| 指導教授： | 張宜武 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年： | 2008 |
| 畢業學年度： | 96 |
| 語文別： | 英文 |
| 論文頁數： | 26 |
| 中文關鍵詞： | 混合超圖 、分離-收縮法 、循環的 |
| 外文關鍵詞： | mixed hypergraph, splitting-contraction algorithm, circular |
| 相關次數： | 點閱：268 下載：52 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在這篇論文中，我們利用分離－收縮法(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.
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
[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.