臺灣博碩士論文加值系統

給定一個圖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. . . . . . . .. . . . . . . . . . . . . . . . . . . . i
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures. . . . . . . . . . . . . . . . . . . . . . . .v
1 Introduction 1
2 Preliminaries 9
2.1 The brunch of tree . . . . . . . . . . . . . . . . . . . . 9
2.2 The avenue and hub . . . . . . . . . . . . . . . . . . . 10
3 Node Searching Problem 13
3.1 Exactly one k-subtree . . . . . . . . . . . . . . . . . . 14
3.1.1 The k-subtree has a k-hub . . . . . . . . . . . . . . . 14
3.1.2 k-subtree has a k-avenue .. . . . . . . . . . . . . . . 17
3.2 Exactly two k-subtrees . . . . . . . . . . . . . . . . . 22
3.2.1 Two k-hubs . . . . . . . . . . . . . . . . . . . . . . .23
3.2.2 Two k-avenues . . . . . . . . . . . . . . . . . . . . .26
3.2.3 One k-hub and one k-avenue . . .. . . . . . . . . . . . 31
3.3 Exactly Three k-subtrees . . . . .. . . . . . . . . . . . 34
3.3.1 Case: ns(Ti;j) = k . . . . . . .. . . . . . . . . . . . 35
3.3.2 Case: ns(Ti;j) = k + 1 . . . . .. . . . . . . . . . . . 35
3.4 More than three k-subtrees . . . .. . . . . . . . . . . . 38
3.4.1 All k-subtrees are k-hub . . . .. . . . . . . . . . . . 38
3.4.2 All k-subtrees have a k-avenue .. . . . . . . . . . . . 41
3.4.3 At least one k-hub and k-avenue . . . . . . . . . . . 42
4 Node Searching Spanning Tree Problem 49
4.1 ns(G) is k + 1 . . . . . . . . . . . . . . . . . . . . . 50
4.1.1 Exactly one k-subtree . . . . . . . . . . . . . . . . . 50
4.1.2 Exactly two k-subtree . . . . . . . . . . . . . . . . . 52
4.1.3 Three or more k-subtrees . . . . . . . . . . . . . . . 58
4.2 ns(G) is k + 2 . . . . . . . . . . . . . . . . . . . . . 60
5 Conclusion and Future Work 63
Bibliography 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 PLANAR
GRAPHS, 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.