博碩士論文 107221004 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:15 、訪客IP:3.142.172.17
姓名 施昀延(Yun-Yen Shih)  查詢紙本館藏   畢業系所 數學系
論文名稱 數樹:方法綜述
(Counting Trees: A Review of Methods)
相關論文
★ 圓環面網路上的病毒散播★ 以2D HP 模型對蛋白質摺疊問題之研究
★ On Steiner centers of graphs★ On the Steiner medians of a block graph
★ 圖形列表著色★ 秩為5的圖形
★ Some results on distance-two labeling of a graph★ 關於非奇異線圖的樹
★ On Minimum Strictly Fundamental Cycle Basis★ 目標集選擇問題
★ 路徑圖與格子圖上的目標集問題★ 超立方體圖與格子圖上的目標集問題
★ 圖形環著色數的若干等價定義★ 網格圖上有效電阻計算方法的比較
★ 拉普拉斯居中度研究概述★ 信息居中度研究簡要回顧
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 數樹的研究是組合最優化的核心問題。大量文獻致力於計算給定的圖中的某些樹結構或森林結構。在這份報告中,我們考慮下列形式的數樹問題:在一個點帶有標號的圖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.
指導教授 葉鴻國 審核日期 2020-7-6
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明