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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:施昀延
研究生(外文):Yun-Yen Shih
論文名稱:數樹:方法綜述
論文名稱(外文):Counting Trees: A Review of Methods
指導教授:葉鴻國
學位類別:碩士
校院名稱:國立中央大學
系所名稱:數學系
學門:數學及統計學門
學類:數學學類
論文出版年:2020
畢業學年度:108
語文別:英文
論文頁數:24
中文關鍵詞:數樹生成樹
相關次數:
  • 被引用被引用:0
  • 點閱點閱:30
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
數樹的研究是組合最優化的核心問題。大量文獻致力於計算給定的圖中的某些樹結構或森林結構。在這份報告中,我們考慮下列形式的數樹問題:在一個點帶有標號的圖G 中,可找到多少棵生成樹?我們在這份報告內,對學界已發表文獻中的數樹方法、定理與其證明做了詳細的整理與回顧。本論文的貢獻在於將這些結果以更簡潔的語言與更圖例式的說明來呈現。
The study counting labeled trees is a central question in combinatorial optimization. A considerable amount of literature has been devoted to count certain trees or forest substructures in the ground graph. In this report, we consider the following form of counting trees questions: Given a graph G with labelled
vertices, how many spanning trees does G contain? In this article, we summarized and reviewed the existing methods and theorems in the published literature that answer this question. We try to give the proofs of the results in a more explanatory and graphic way.
1 Introduction and preliminaries 1
2 Counting Spanning Forests 2
3 Counting Rooted Directed Trees 4
4 Matrix Tree Theorem via Deletion Contraction Recurrence 7
5 Cayley's Formula via Prüfer Code 10
6 Cayley's Formula via Joyal's Combinatorial Argument 12
7 Counting Weighted Rooted Directed Trees 14
References 17
[1] Ravindra B. Bapat, Graphs and Matrices, Universitext, Springer-Verlag London, 2014.
[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, The Macmillan Press Ltd, London, 1976.
[3] J.A. Bondy and U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics vol. 244, 2008.
[4] Seth Chaiken, A combinatorial proof of the all minors matrix tree theorem, SIAM J. Alg. Disc. Meth. (1982) 319-329.
[5] S. Chaiken and D.J. Kleitman, Matrix tree theorems, J. Combin. Theory Ser. A 24 (3) (1978) 377-381.
[6] Nicholas A. Loehr, Bijective Combinatorics, CRC Press Chapman Hall, 2010.
[7] André Joyal, Une théorie combinatoire des séries formelles, Advances in Mathematics 42 (1981),1-82.
[8] J.W. Moon, Some determinant expansions and the matrix-tree theorem, Discrete Math. 124 (1994) 163-171.
[9] H. Prüfer, Neuer Beweis eines Satzes über Permutationen, Arch. Math. Phys. 27 (1918) 142-144.
[10] W.T. Tutte, Graph Theory, Addison-Wesley,1984.
[11] Hong-Gwa Yeh, Class Notes for Graph Theory, Spring 2020, National Central University, Taiwan.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔