DC 欄位 值 語言 DC.contributor 數學系 zh_TW DC.creator 江俊瑩 zh_TW DC.creator Chun-ying Chiang en_US dc.date.accessioned 2012-6-28T07:39:07Z dc.date.available 2012-6-28T07:39:07Z dc.date.issued 2012 dc.identifier.uri http://ir.lib.ncu.edu.tw:88/thesis/view_etd.asp?URN=952401002 dc.contributor.department 數學系 zh_TW DC.description 國立中央大學 zh_TW DC.description National Central University en_US dc.description.abstract 在本篇論文裡，我們在不同的圖上考慮目標集選擇問題(target set selection problem)。 在第二章，我們證明了在任意閾值(thresholds)的區塊仙人掌圖(block-cactus graphs)以及閾值小於等於2的弦圖(chordal graph)上，目標集選擇問題可以在線性時間內解決。當考慮閾值為2的漢米圖(Hamming graphs)時，我們可以給出一個最佳解。在第三章，我們考慮的是閾值為2的cycle permutation graphs和廣義彼得森圖形。在第四章，對於閾值為3的torus cordalis 與torus serpentinus的最佳解，提出一個改進的上界。在第五章，我們考慮以下幾種蜂巢狀網路在strict majority thresholds下的目標集選擇問題：蜂巢式網格(honeycomb mesh)、蜂巢式環形曲面(honeycomb torus)、蜂巢式矩形環形曲面(honeycomb rectangular torus)、蜂巢式菱形環形曲面(honeycomb rhombic torus)、廣義蜂巢式環形曲面(generalized honeycomb torus)以及六角網格(hexagonal grids)。在第六章，我們研究多邊形拼圖在strict majority thresholds下的目標集選擇問題。 zh_TW dc.description.abstract In this thesis, We are interested in the target set selection problem on different kinds of graphs. In Chapter 2, we show that if G is a block-cactus graph with general thresholds, then the TARGET SET SELECTION problem can be solved in linear time. When G is a chordal graph with thresholds heta(v) leq 2 for each vertex v in G, then the problem can also be solved in linear time. We precisely determine an optimal target set for a Hamming graph G with constant threshold heta(v) = 2 for each vertex v in G. In Chapter 3, we determine an optimal target set for (G,2) where G is a cycle permutation graph or a generalized Petersen graph. In Chapter 4, we present some improved upper bounds and exact values for the parameters min-seed(C_m oslash C_n,3) and min-seed(C_m otimes C_n,3). In Chapter 5, we study the TARGET SET SELECTION problem under strict majority thresholds on different kinds of honeycomb networks such as honeycomb mesh HM_t, honeycomb torus HT_t, honeycomb rectangular torus HReT(m,n), honeycomb rhombic torus HRoT(m,n), generalized honeycomb rectangular torus GHT(m,n,d) and three kinds of hexagonal grids (planar, cylindrical, and toroidal). In Chapter 6, we determine minimum target sets for several tilings of the plane under strict majority threshold. en_US DC.subject 區塊仙人掌圖 zh_TW DC.subject 擴散 zh_TW DC.subject 社群網路 zh_TW DC.subject 目標集選擇 zh_TW DC.subject 六角網格 zh_TW DC.subject 弦圖 zh_TW DC.subject 漢米圖 zh_TW DC.subject 環面 zh_TW DC.subject 蜂巢狀網路 zh_TW DC.subject honeycomb networks en_US DC.subject chordal graph en_US DC.subject block-cactus graph en_US DC.subject diffusion en_US DC.subject social networks en_US DC.subject target set selection en_US DC.subject tori en_US DC.subject Hamming graph en_US DC.subject hexagonal grid en_US DC.title 目標集選擇問題 zh_TW dc.language.iso zh-TW zh-TW DC.title On the target set selection problem en_US DC.type 博碩士論文 zh_TW DC.type thesis en_US DC.publisher National Central University en_US