Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 對偶超圖之著色數探討
The Chromatic Number of A Dual Hypergraph
作者 莊佳芬
Jhuang, Jia-Fen
貢獻者 張宜武
Chang, Yi-Wu
莊佳芬
Jhuang, Jia-Fen
關鍵詞 對偶超圖
同構
Dual hypergraph
Transversal number
Isomorphism
日期 2004
上傳時間 18-Sep-2009 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
dc.contributor.advisor 張宜武zh_TW
dc.contributor.advisor Chang, Yi-Wuen_US
dc.contributor.author (Authors) 莊佳芬zh_TW
dc.contributor.author (Authors) Jhuang, Jia-Fenen_US
dc.creator (作者) 莊佳芬zh_TW
dc.creator (作者) Jhuang, Jia-Fenen_US
dc.date (日期) 2004en_US
dc.date.accessioned 18-Sep-2009 18:29:06 (UTC+8)-
dc.date.available 18-Sep-2009 18:29:06 (UTC+8)-
dc.date.issued (上傳時間) 18-Sep-2009 18:29:06 (UTC+8)-
dc.identifier (Other Identifiers) G0917510131en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/36402-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 應用數學研究所zh_TW
dc.description (描述) 91751013zh_TW
dc.description (描述) 93zh_TW
dc.description.abstract (摘要) 本文藉構造bipartite graph 的形式討論超圖與對偶超圖的transversal number,進而探討最小著色數的上界,以及證明出此兩圖的最小著色數可差異很大,也可用此方法構造出想要的最小著色數之差異。最後探討在某些情形下,超圖與其對偶超圖的同構性,再則整理出其必要條件。zh_TW
dc.description.abstract (摘要) 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 .en_US
dc.description.abstract (摘要) 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
-
dc.description.tableofcontents 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
zh_TW
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0917510131en_US
dc.subject (關鍵詞) 對偶超圖zh_TW
dc.subject (關鍵詞) 同構zh_TW
dc.subject (關鍵詞) Dual hypergraphen_US
dc.subject (關鍵詞) Transversal numberen_US
dc.subject (關鍵詞) Isomorphismen_US
dc.title (題名) 對偶超圖之著色數探討zh_TW
dc.title (題名) The Chromatic Number of A Dual Hypergraphen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] Claude Berge. (1973). ""Graphs and hypergraphs"" North-Hollandzh_TW
dc.relation.reference (參考文獻) [2] Claude Berge. (1989). ""Hypergraphs"" North-Hollandzh_TW
dc.relation.reference (參考文獻) [3] Voloshin, V.~I. (1995). ""On the upper chromatic number of a hypergraph`` Australasian Journal of Combinatorics, 25--45.zh_TW
dc.relation.reference (參考文獻) [4] Voloshin, V. I. (2002). ""Coloring mixed hypergraphs: theorey, algorithms andzh_TW
dc.relation.reference (參考文獻) applications`` American Mathematical Societyzh_TW
dc.relation.reference (參考文獻) [5] Bulgaru, M., and Voloshin, V.~I. (1997). ""Mixed interval hypergraphs`` Discrete Applied Mathematics, 77,29--41.zh_TW
dc.relation.reference (參考文獻) [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.zh_TW
dc.relation.reference (參考文獻) [7] Kr\\`{a}l`, D., Kratochv\\`{i}l, J., and Voss, H.~J. (2004). ""Mixed hypercacti,`` Discrete Math., 286, 99--113.zh_TW
dc.relation.reference (參考文獻) [8] Gionfriddo, M., Milazzo, L., and Voloshin, V. (2002). ""On the upper chromatic index of a multigraph,`` Comput. Sci.J.Moldova,81--91zh_TW