# 臺灣博碩士論文加值系統

(98.82.140.17) 您好！臺灣時間：2024/09/08 06:59

:::

### 詳目顯示

:

• 被引用:0
• 點閱:152
• 評分:
• 下載:0
• 書目收藏:0
 給定一個圖G，點搜尋問題的目標是求出在點搜尋的規則下，求出可以保證清除圖G所需的最小搜尋者數。我們稱所需的最小搜尋者數為點搜尋數。點搜尋生成樹問題則是在圖G的所有可能的生成樹中，找出點搜尋數最小的生成樹。本篇論文旨在單迴圈圖上，對點搜尋問題和點搜尋生成樹問題進行研究。我們可以將單迴圈圖看作是一個樹狀圖加上一個額外的邊，而那個邊將會在原本的樹狀圖上形成迴圈，反過來說，單迴圈圖上所有可能的生成樹都可以藉由刪去迴圈上的某個邊求得。從前人的研究中，已知可以在O(n)的時間內求取樹狀圖的點搜尋樹，所以我們用很直覺得方法在O(n^2)的時間內解決單迴圈圖上的點搜尋生成樹問題。在本篇論文中，我們提出了可以在O(n)的時間內解決單迴圈上的點搜尋生成樹的演算法。
 The node searching problem on a graph G is to determine the minimum number of searchers to clear G via rules of node searching. This minimum number is called the node-search number of G. The node searching spanning tree problem on graph G is to find a spanning tree T of G such that the node-search number of T is the minimum among all possible spanning trees of G. In this thesis, we study the node searching spanning tree problem on unicyclic graphs. A unicyclic graph is a tree with an additional edge. That is, a unicyclic graph contains only one cycle. It is known that the node searching problem on trees can be solved in O(n) time, where n is the number of vertices in the tree. Thus, a straightforward algorithm for solving the node searching spanning tree problem on unicyclic graphs runs in O(n2) time. In this study, we present a linear-time algorithm for solving the node searching spanning tree problem on unicyclic graphs.
 Abstract. . . . . . . .. . . . . . . . . . . . . . . . . . . . iContents . . . . . . . . . . . . . . . . . . . . . . . . . . iiiList of Figures. . . . . . . . . . . . . . . . . . . . . . . .v1 Introduction 12 Preliminaries 92.1 The brunch of tree . . . . . . . . . . . . . . . . . . . . 92.2 The avenue and hub . . . . . . . . . . . . . . . . . . . 103 Node Searching Problem 133.1 Exactly one k-subtree . . . . . . . . . . . . . . . . . . 143.1.1 The k-subtree has a k-hub . . . . . . . . . . . . . . . 143.1.2 k-subtree has a k-avenue .. . . . . . . . . . . . . . . 173.2 Exactly two k-subtrees . . . . . . . . . . . . . . . . . 223.2.1 Two k-hubs . . . . . . . . . . . . . . . . . . . . . . .233.2.2 Two k-avenues . . . . . . . . . . . . . . . . . . . . .263.2.3 One k-hub and one k-avenue . . .. . . . . . . . . . . . 313.3 Exactly Three k-subtrees . . . . .. . . . . . . . . . . . 343.3.1 Case: ns(Ti;j) = k . . . . . . .. . . . . . . . . . . . 353.3.2 Case: ns(Ti;j) = k + 1 . . . . .. . . . . . . . . . . . 353.4 More than three k-subtrees . . . .. . . . . . . . . . . . 383.4.1 All k-subtrees are k-hub . . . .. . . . . . . . . . . . 383.4.2 All k-subtrees have a k-avenue .. . . . . . . . . . . . 413.4.3 At least one k-hub and k-avenue . . . . . . . . . . . 424 Node Searching Spanning Tree Problem 494.1 ns(G) is k + 1 . . . . . . . . . . . . . . . . . . . . . 504.1.1 Exactly one k-subtree . . . . . . . . . . . . . . . . . 504.1.2 Exactly two k-subtree . . . . . . . . . . . . . . . . . 524.1.3 Three or more k-subtrees . . . . . . . . . . . . . . . 584.2 ns(G) is k + 2 . . . . . . . . . . . . . . . . . . . . . 605 Conclusion and Future Work 63Bibliography 65
 [1] M. Aigner and M. Fromme, A game of cops and robbers, Discrete Applied Math ematics 8 (1984) 111.[2] B. Alspach, Sweeping and searching in graphs: a brief survey, Matematiche 59 (2006) 537.[3] O. Amini, F. Huc, and S. Pérennes, ON THE PATH-WIDTH OF PLANARGRAPHS, SIAM J. DISCRETE MATH., Vol. 23, No. 3, pp. 13111316,2009.[4] H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, Volume 209, Issues 12, 6 December 1998, Pages 145.[5] A. Bonato, R.J. Nowakowski, The Game of Cops and Robbers on Graphs, Student Mathematical Library, vol. 61, American Mathematical Society, Providence, RI (2011).[6] R. Breisch, An intuitive approach to speleotopology, southwestern Cavers (A publication of the Southwestern Region of the National Speleological Society) VI (1967) 7278.[7] H.-H. Chou, M.-T. Ko, C.-W. Ho, and G.-H. Chen, Node-searching problem on block graphs, Discrete Applied Mathematics, Volume 156, Issue 1, 1 January 2008, Pages 5575.[8] J. A. Ellis and M. Markov, Computing the vertex separation of unicyclic graphs, Information and Computation, 192: 123161, 2004.[9] J. A. Ellis, I. H. Sudborough, and J. S. Turner, The vertex separation and search number of a graph, Information and Computation, 113(1): 5079, 1994.[10] F. V. Fomin, P. A. Golovach, J. Kratochvil, N. Nisse, and K. Suchan, Pursuing a fast robber on a graph, Theoretical Computer Science, Volume 411, Issues 79, Pages 11671181, 28 February 2010.[11] J. Gusted, On the pathwidth of chordal graphs, Discrete Applied Mathematics, Volume 45, Issue 3, 7 September 1993, Pages 233248.[12] G. Hahn, Cops, robbers and graphs, Tatra Mountain Mathematical Publications 36 (2007) 163176.[13] R. Isaacs. Dierential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization (New York: John Wiley & Sons) (1965).[14] T. Ishida and R. Korf, Moving target search, In Proceedings of International Joint Conference in Arti-cial Intelligence, pages 204211, 1991.[15] A. Kehagias, G. A. Hollinger and A. Gelastopoulos, Searching the Nodes of a Graph: Theory and Algorithms, CoRR, abs/0905.3359, 2009.[16] N. G. Kinnersley, The vertex separation number of a graph equals its path-width, Information Processing Letters 42 (6), 345350,1992.[17] L. M. Kirousis, Interval graphs and seatching, Discrete Mathematics, Volume 55, Issue 2, July 1985, Pages 181184.[18] L. M. Kirousis and C. H. Papadimitriou, Searching and Pebbling, Theoretical Computer Science, 47, pp. 205216,1986.[19] P. S. Kumar and C. E. V. Madhavan, Minimal vertex separators of chordal graphs, Discrete Applied Mathematics, Volume 89, Issues 13, Pages 155168, 1998.[20] T. Lengauer, Black-White Pebbles and Graph Separation, Acta Informatica, 16:465475, 1981.[21] M. Li, New algorithms for pathwidth computation, (2004) Doctoral, Rice University, http://hdl.handle.net/1911/18662.[22] B. Monien and I.H. Sudborough, Min cut is NP-complete for edge weighted trees, Theoret. Comput. Sci., 58 (13), pp. 209229, 1988.[23] R. Nowakowski and R. P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math, 43, pp 235239,1983.[24] T. D. Parsons, Pursuit-evasion in a graph, Theory and Applications of Graphs, Springer-Verlag. 426441, 1976.[25] T.D. Parsons, The search number of a connect graph, Proc, 9th S-E Conf. on Combinatatorics, Graph Theory, and Compueing, 459554,1978.[26] S.-L. Peng, C.-Y. Tang, and M.-T. Ko, A study of graph searching on special graphs, PhD. desertation, 1999[27] S.-L. Peng, C.-W. Ho, T.-s. Hsu, M.-T. Ko and C. Y. Tang, Edge and node searching problems on trees, Theoretical Computer Science 240 (2000) 429-446.[28] S.-L. Peng, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu, and Chuan-Yi Tang, Graph searching on chordal graphs, Algorithms and Computation, Volume 1178 of the series Lecture Notes in Computer Science pp 156165, 2005.[29] N. N. Petrov, Pursuit problems without information about the evader, Dierents. Uravn., 18(1982), NO. 8, 13451352.[30] A. Quilliot, Jeux et pointes xes sur les graphes, Thése de 3eme cycle, Universite de Paris VI, pp.131145, 1978.[31] P. Scheer, A linear algorithm for pathwidth of trees, in: R. Bodendiek and R.Henn, eds., Topics in Combinatorics and Graph Theory (Physica-Verlag, Hei delberg, 1990), 613620.[32] K. Skodinis, Computing optimal linear layouts of trees in linear time, In Paterson, M., editor, Algorithms ESA 2000, volume 1879 of Lecture Notes in Computer Science, pages 403414, SpringerVerlag, 2000.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 分離性全支配問題在環面和格子圖上之研究 2 圖形相似度問題之研究 3 最大化雲端計算虛擬機器使用率 4 圖形的平衡連通分群問題之研究 5 路由波長分配問題在一維陣列光纖網路之研究 6 連通圖形搜尋在樹上之研究 7 掌性催化劑的合成與應用 8 透過高壓技術應用於紅外光譜來探討離子液體與木質素之間的作用力關係 9 含二硫(硒)磷酸配位基之多氫銅金屬簇的合成與配體交換之研究 10 領導型態對企業文化、企業倫理、企業績效之影響以經濟部所屬國營事業花蓮區域為例 11 睡眠呼吸障礙程度評估與動態生理指標臨床研究 12 運動覺對棒球短打技能的影響 13 負債的回饋：一位田徑教師的信念實踐 14 子承父業-三位體育教師對子女參與運動代表隊經驗之研究 15 運動與文學家-村上春樹的運動生活實踐

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室