| 研究生: |
莊佳芬 Jhuang, Jia-Fen |
|---|---|
| 論文名稱: |
對偶超圖之著色數探討 The Chromatic Number of A Dual Hypergraph |
| 指導教授: |
張宜武
Chang, Yi-Wu |
| 學位類別: |
碩士
Master |
| 系所名稱: |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年: | 2005 |
| 畢業學年度: | 93 |
| 語文別: | 英文 |
| 論文頁數: | 19 |
| 中文關鍵詞: | 對偶超圖 、同構 |
| 外文關鍵詞: | Dual hypergraph, Transversal number |
| 相關次數: | 點閱:174 下載:23 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本文藉構造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