Loading...
|
Please use this identifier to cite or link to this item:
https://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: | [應用數學系] 學位論文
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
