請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48605
標題: | 在圍長為g之簡單有向圖上之動態壟斷 Dynamic Monopoly in Simple Directed Graphs with Girth g |
作者: | Wei-Chih Huang 黃韋誌 |
指導教授: | 呂育道(Yuh-Dauh Lyuu) |
關鍵字: | 演算法,圖論,動態壟斷, algorithm,graph theory,dynamic monopoly, |
出版年 : | 2010 |
學位: | 碩士 |
摘要: | 假設G(V,E)為一簡單有向圖(simple directed graph),意即圖中任兩點(vertex)之間最多只存在一條邊(edge),每一條邊皆有一個方向。若G(V,E)之最短迴圈之長度為 ,則稱G(V,E)之圍長(girth)為g。此外,我們額外限制在簡單有向圖上每一點皆至少有一個內鄰(in-neighbor)。考慮以下有向圖上的擴散過程:最初,一些圖上的點處於已啟動(active)狀態,這些初始化為已啟動的點稱之為種子(seed);而其他點則為未啟動(inactive)狀態。當一個未啟動的點有過半的內鄰為已啟動狀態時,則該點亦會被啟動(activated)。而依此規則,擴散過程將持續至沒有其他未啟動的點可被啟動為止,此過程即為動態壟斷。在動態壟斷(dynamic monopoly)問題之中,我們注重的是:在擴散過程中,可以啟動所有點的種子集合。而本論文推導出在圍長為g之簡單有向圖G(V,E)中,最小可啟動所有點的種子集合之大小上限為 floor(|V|/2)+ceiling(|V|/2g)。 Suppose G(V,E) is a simple directed graph, where there is at most one directed edge between each pair of vertices. We say G(V,E) has girth g if the length of the shortest cycle in is . We shall require that each vertex in a simple directed graph have at least one in-neighbor. Now, consider a process of propagations in a directed graph G(V,E) as follows. Some vertices, called seeds, in V are initially active, and the others are inactive. Later, an inactive vertex is activated if over half of its in-neighbors are active, and such activations end while no more vertices can be activated. In dynamic monopoly problems, we focus on such a set of seeds in V that all vertices will be activated at the end of propagations. In this thesis, we derive an upper bound, floor(|V|/2)+ceiling(|V|/2g), on size of such a set of seeds for any simple directed graph G(V,E) with girth g. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48605 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 423.55 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。