Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/36402
|
| Title: | 對偶超圖之著色數探討
The Chromatic Number of A Dual Hypergraph |
| Authors: | 莊佳芬
Jhuang, Jia-Fen |
| Contributors: | 張宜武
Chang, Yi-Wu
莊佳芬
Jhuang, Jia-Fen |
| Keywords: | 對偶超圖
同構
Dual hypergraph
Transversal number
Isomorphism |
| Date: | 2004 |
| Issue Date: | 2009-09-18 18:29:06 (UTC+8) |
| Abstract: | 本文藉構造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 |
| Reference: | [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 |
| Description: | 碩士
國立政治大學
應用數學研究所
91751013
93 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0917510131 |
| Data Type: | thesis |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| index.html | 0Kb | HTML2 | 417 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
