資料載入中.....
|
請使用永久網址來引用或連結此文件:
https://nccur.lib.nccu.edu.tw/handle/140.119/36402
|
| 題名: | 對偶超圖之著色數探討
The Chromatic Number of A Dual Hypergraph |
| 作者: | 莊佳芬
Jhuang, Jia-Fen |
| 貢獻者: | 張宜武
Chang, Yi-Wu
莊佳芬
Jhuang, Jia-Fen |
| 關鍵詞: | 對偶超圖
同構
Dual hypergraph
Transversal number
Isomorphism |
| 日期: | 2004 |
| 上傳時間: | 2009-09-18 18:29:06 (UTC+8) |
| 摘要: | 本文藉構造bipartite graph 的形式討論超圖與對偶超圖的transversal number，進而探討最小著色數的上界，以及證明出此兩圖的最小著色數可差異很大，也可用此方法構造出想要的最小著色數之差異。最後探討在某些情形下，超圖與其對偶超圖的同構性，再則整理出其必要條件。
H=(X,D) is called a hypergraph, where X is the vertex set and D is a family of subsets of X, denoted as D-edges, and we assume that every D-edges have at least two elements. A strict t-coloring is a onto mapping from X to {1,2,....,t} such that each D contained in D-edge set has two vertices having distinct values. The maximum(minimum) number of colors over all strict k-coloring is called the upper(lower) chromatic number and is denoted as .
Abstract.......................................................i
1.Introduction.................................................1
2.The difference between the transversal numbers of H and H*...4
3.Isomorphism.................................................12
4.Conclusions.................................................16
References....................................................17 |
| 參考文獻: | [1] Claude Berge. (1973). ""Graphs and hypergraphs"" North-Holland
[2] Claude Berge. (1989). ""Hypergraphs"" North-Holland
[3] Voloshin, V.~I. (1995). ""On the upper chromatic number of a hypergraph`` Australasian Journal of Combinatorics, 25--45.
[4] Voloshin, V. I. (2002). ""Coloring mixed hypergraphs: theorey, algorithms and
applications`` American Mathematical Society
[5] Bulgaru, M., and Voloshin, V.~I. (1997). ""Mixed interval hypergraphs`` Discrete Applied Mathematics, 77,29--41.
[6] Jiang, T., Mubayi, D., Tuza, Z., Voloshin, V., and West, D.~B.(2003). ""The chromatic spectrum of mixed hypergraphs,``Graphs and Combinatorics, 309--318.
[7] Kr\\`{a}l`, D., Kratochv\\`{i}l, J., and Voss, H.~J. (2004). ""Mixed hypercacti,`` Discrete Math., 286, 99--113.
[8] Gionfriddo, M., Milazzo, L., and Voloshin, V. (2002). ""On the upper chromatic index of a multigraph,`` Comput. Sci.J.Moldova,81--91 |
| 描述: | 碩士
國立政治大學
應用數學研究所
91751013
93 |
| 資料來源: | http://thesis.lib.nccu.edu.tw/record/#G0917510131 |
| 資料類型: | thesis |
| 顯示於類別: | [應用數學系] 學位論文
|
文件中的檔案:
| 檔案 |
大小 | 格式 | 瀏覽次數 |
|---|
| index.html | 0Kb | HTML2 | 584 | 檢視/開啟 |
|
在政大典藏中所有的資料項目都受到原著作權保護.
|
