請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/83893
標題: | 證明最小生成樹環交集問題之猜想 Proof of a Conjecture about Minimum Spanning Tree Cycle Intersection |
作者: | Min-Jen Chen 陳泯臻 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 圖,生成樹,環, Graph,Spanning Tree,Cycle, |
出版年 : | 2022 |
學位: | 碩士 |
摘要: | 給定一圖G和其一生成樹T,每條在G-T的邊e會在T∪{e}中產生一個環,我們把那些邊稱作環邊;那些環稱作樹環。兩個樹環的交集為其所有共有的邊形成的集合,若兩相異樹環的交集是非空的,我們將其視為一次交集。生成樹T的樹交集數為其所有樹環的交集次數。 最小生成樹環交集問題旨在找出圖的所有生成樹中樹交集數最小的生成樹。Dubinsky等人提出一猜想,此猜想敘述為若一圖有一星形生成樹,星形生成樹為其中一點和其它所有點都相鄰的生成樹,則此星形生成樹有最小的樹交集數。在此論文中,我們證明此猜想,並探討其延伸的可能性。 Let G be a graph and T a spanning tree of G. For an edge e in G?T, there is a cycle in T∪{e}. We call those edges cycle-edges and those cycles tree-cycles. The intersection of two tree-cycles is the set of all edges in common. If the intersection of two distinct tree-cycles is not empty, we regard that as an intersection. The tree intersection number of T is the number of intersections among all tree-cycles of T. The Minimum Spanning Tree Cycle Intersection (MSTCI) problem aims to find a spanning tree with minimum tree intersection number among all possible spanning trees. In this thesis, we prove the conjecture, posed by Dubinsky et al., which states that if a graph admits a star spanning tree in which one vertex is adjacent to all other vertices, then the star spanning tree has the minimum tree intersection number and investigate the possibility of generalizing the conjecture. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/83893 |
DOI: | 10.6342/NTU202201520 |
全文授權: | 未授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1807202211143700.pdf 目前未授權公開取用 | 914.38 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。