請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50082
標題: | 大眾化生成樹問題 On the Popular Spanning Tree Problem |
作者: | Wei-Cheng Lin 林蔚城 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 生成樹,投票理論, spanning trees,voting theory, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | 生成樹問題向來是離散數學與演算法領域中經典的最佳化問題。常應用於現代網路模型及協定之建構,探討如何在最小成本情況下使得各節點之間具連通的功能。而本論文所提出的生成樹,希望從相關傳統問題尋常切入的兩個方向(最小化最大以及最小化總和)外,發展出另一套與投票理論相遇之模型。我們將問題的定義回歸到每個節點自身的需求上。這些需求可能是從自己走到樹中最遠點的距離,也可能是經過樹中每個點的距離總和,或是在樹中與自己相鄰的點數等。我們根據一些初步觀察到的性質,提出在某些情況下有效率的算法,探討如何尋找一棵儘可能滿足大眾偏好的生成樹。 Given an undirected connected graph G = (V, E) we consider the prob-lem of finding a spanning tree of G which preferred by the majority. We called it popular spanning trees problem (PST) and Condorcet spanning trees prob-lem (CST). In this thesis we mainly focus on when voter’s preference criteria is eccentricity on trees. On cycles, we show that finding a PST or verifying if a PST exists can be done in O(|V |2) time. On unit distance graph, we show that finding a PST or verifying if a PST exists can be done in O(|E|3) time, and for the special case where the center is unique, the shortest-path tree from it is a popular spanning tree. On general graphs, when absolute 1-center and Plural point coincide, the shortest-path tree from it is a popular spanning tree. Similarly, when absolute 1-center and Condorcet point coincide, the shortest-path tree from it is a Condorcet spanning tree. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50082 |
DOI: | 10.6342/NTU201601989 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 894.16 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。