(3.238.235.155) 您好!臺灣時間:2021/05/11 02:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳韋男
論文名稱:著色多項式
論文名稱(外文):Chromatic polynomials in graph theory
指導教授:王心如
學位類別:碩士
校院名稱:國立中正大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:英文
論文頁數:31
中文關鍵詞:著色多項式
外文關鍵詞:Chromatic polynomials
相關次數:
  • 被引用被引用:0
  • 點閱點閱:304
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文主要是介紹圖形學中的著色多項式(chromatic polynomials),以及如何求得各圖形的著色多項式的方法。以下為此論文所應用的主要內容:
第一章:刪除-結合法(deletion-contraction method)。
第二章:介紹二部完全圖(complete bipartite graph)、錐圖(pyramid)及雙錐圖(double pyramid)的著色多項式。
第三章:利用圖的秩矩陣(rank matrix)求著色多項式。
第四章:介紹不可分的誘導子圖(non-separable induced subgraphs)的乘積表示式,並依此求得著色多項式。

Chapter 0 :Introduction2
Chapter 1 :The deletion-contraction method7
1.1The definition of chromatic polynomial7
1.2Basic properties of chromatic polynomial8
1.3The deletion-contraction method9
Chapter 2:Chromatic polynomial of join of two graphs14
2.1Chromatic polynomial of the complete bipartite graph Km,n14
2.2Chromatic polynomial of the pyramid Wn and the double pyramid Πn16
Chapter 3 :The rank polynomial18
Chapter 4 :The multiplicative expansion23
4.1The non-separable subgraph expansion23
4.2The induced subgraph expansion25
Appendix30
Reference31

[B1] Baker G.A. Linked-cluster expansion in graph-vertex coloration problem, JCT(B) 10(1971), 217-231.
[B2] Biggs, N.L. Expansion of the chromatic polynomial, Discrete Math, 6(1973), 105-113.
[B2-1] Biggs, N.L. On cluster expansions in graph theory and physics, Quart. J. Math. (Oxford) 29(1978), 159-173.
[B3] Birkhoff and Lewis, Chromatic polynomials.Math. Soc.60 (1964), 355-451.
[B3-1] Birkhoff, G.D. (1912) A determinant formula for the number ways of coloring a map. Ann. Math. 14, 42-46.
[H1] Harary Frank. Graph theory. Chapter 12(1969) 145-148.
[H2] Heawood, P. J. Map colour theorems. Quart.J.Math.24 (1890), 332-338.
[K1] Kempe, A. B. On the geographical problem of four colors. Amer. J. Math.2 (1879), 193-204.
[M1] May, K. O. The origin of four-color conjecture. Isis 56 (1965), 346-348.
[N1] Norman Biggs. Algebraic graph theory. Part 2(1993) 63-80.
[O1] Ore and Stemple, Numerical methods in the four color problem. Recent progress in Combinatorics (W. T. Tutte, ed.) Academic Press, New York, (1969).
[R1] Rota, On the foundations of combinatorial theory, I: Theory of functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340-368.
[T1] Tutte, W.T. On dichromatic polynomials, JCT 2(1967), 301-320.
[W1-1] Whitney, H. (1932) A logical expansion in mathematics, Bull. Amer. Math. Soc. 38, 572-579.
[W1-2] Whitney, H. (1932) The coloring of graphs, Ann. Math. 33, 688-718.
[W1-3] Whitney, The coloring of graphs. Ann. Math. (2) 33 (1932), 688-718.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔