Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/158372
|
| Title: | 多標記樹的漸進分析
Asymptotics of Leaf-Multi-Labeled Trees |
| Authors: | 張維霽
Chang, Wei-Chi |
| Contributors: | 符麥克
Michael Fuchs
張維霽
Chang, Wei-Chi |
| Keywords: | 漸進分析
漸進行為
多標記樹
二元樹
至少二元的樹
無標記樹
Asymptotics
asymptotic behavior
multi-labeled trees
binary trees
non-binary trees
unlabeled trees |
| Date: | 2025 |
| Issue Date: | 2025-08-04 13:11:04 (UTC+8) |
| Abstract: | 多標記樹, 也就是從固定的集合用正整數標記葉子的樹, 不但在生物學的演化上有多樣的應用, 而且也是無標記樹的推廣, 它們的實際和漸進計數在組合學是一個古典的主題。
Czabarka et al.等人推導了多標記樹的生成函數。 這篇論文的目標是解釋他們的結果而且用這些結果找到二元樹和至少二元之多標記樹的漸進展開式。除此之外, 我們證明主要項當中的常數之漸進展開式 (當標記的數量趨近無窮時) 而且構思有效率的程序以估計它們。 我們也會給出計數和估計值的表格。
這篇論文的短大綱如以下所述：
在第一章, 我們將從圖論裡的一些定義開始, 尤其是樹和圖有關聯的部分。1.2節的主要篇幅將會是singularity分析, 因為它在推導漸進式扮演著核心之角色。
在第二章, 我們將更詳細地解釋Czabarka et al.等人對於多標記樹的生成函數之結果。我們也將會給有
根二元無標記樹的表格 (包含實際值和估計值)。此外,我們將在定理11用符號組合之方法簡化他們的證明。
在第三章,我們將用前兩章之背景推導四種多標記樹 (包含有根二元、無根二元、有根至少二元、無根至少二元)數量的漸進式。我們也將推導當標記集合趨近無窮時,常數項之漸進展開式。
Multi-labeled trees, i.e., trees with leaves labeled with positive integers from a fixed set, are not only important in diverse applications in evolutionary biology, but are generalizations of unlabeled trees whose exact and asymptotic enumeration is a classical topic in combinatorics.
Czabarka et al. derived generating functions of multi-labeled trees. The goal of this thesis is to explain their results and use them to find asymptotic expansions of the counts of binary and non-binary multi-labeled trees. Moreover, we prove asymptotic expansions of the constants in the main term of the asymptotics (as the number of labels tends to infinity) and devise efficient procedures to approximate them. Tables of the counts and the approximations are given as well.
A short outline of the thesis is as follows:
In Chapter 1, we will begin with some definitions from graph theory, in particular those related to trees and graphs. The main context of Section 1.2 will be singularity analysis, as it plays a central role in deriving asymptotics.
In Chapter 2, we will explain Czabarka et al.'s results of generating functions for multi-labeled trees in more detail. We will also give the table of numbers of rooted binary unlabeled trees containing both exact values and approximations. Furthermore, we will simplify their proof in Theorem 11 with methods from symbolic combinatorics.
In Chapter 3, we will derive the asymptotics of the number of four kinds of multi-labeled trees based on the background in the previous two chapters, including rooted binary, unrooted binary, rooted non-binary, and unrooted non-binary ones. We will also derive the asymptotic expansions of constants as the labeled set approaches infinity. Moreover, we will give some tables of the counts and discuss approximation methods. |
| Reference: | [1] É.Czabarka, P. L. Erdős, V. Johnson, V. Moulton (2013). Generating functions for multi-labeled trees, Discrete Applied Mathematics, 161:1-2, 107--117.
[2] V. P. Johnson. Enumeration Results on Leaf-labeled Trees (Ph.D thesis), 2012.
[3] Analytic Combinatorics, Cambridge University Press, 2009.
[4] J. H. van Lint and R. M. Wilson. A Course in Combinatorics, second edition, 2001.
[5] Douglas B. West. Introduction to Graph Theory, second edition, Pearson Education Taiwan Ltd., 2011.
[6] OpenAI (2025). https://chat.openai.com
[7] 微積分學習要訣, 第20版, 劉明昌著, 2020年9月 |
| Description: | 碩士
國立政治大學
應用數學系
112751018 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0112751018 |
| Data Type: | thesis |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 101801.pdf | | 546Kb | Adobe PDF | 0 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
