臺灣博碩士論文加值系統

令 G = (V, E) 為一無向圖 (undirected graph) 或有向圖 (directed graph)。令 n = |V| 且 m = |E|。將 G 的所有延伸樹 (spanning tree) 列舉 (enumerate) 出來是一個相當古老的問題，從 1968 年開始，就有 Gabow和Tarjan 等大師開始對這個問題進行研究。
當 G 為無向圖時，在 1997 年的時候，Shioura、Tamura 和 Uno 就已提出了將 G 的所有延伸樹列舉出來的最佳化 (optimal) 演算法。這裡所謂的最佳化指的是這個演算法的時間複雜度 (time complexity)，執行時的空間複雜度 (space complexity)，以及輸出所需要用到的空間複雜度 (output size complexity) 都已經是最好的。
當 G 為有向圖時，這個問題一直都沒有最佳化的演算法。在有向圖中，延伸樹的定義為：在一個延伸樹中，其根 (root) 到每一個其它的vertex 都有一條唯一的路徑 (path)。在 2000 年時，Kapoor 和 Ramesh 提出了一個輸出空間複雜度是 O(N + n^2) 的演算法，這樣的輸出空間複雜度是目前最好的；但是這一個演算法在執行中卻須要用到 O(n^2) 的空間。N 為 G 中所有延伸樹的個數。
在這篇論文中，我們提出了一個將有向圖中所有延伸樹都列舉出來的演算法，這一個演算法使用了 Kapoor 和 Ramesh 所提出的 “edge-exchange” 技術，只要把目前所列舉到的延伸樹換一根 edge 就可以產生出另一個新的延伸樹。這一個演算法的輸出空間複雜度跟Kapoor 和 Ramesh的演算法一樣，都是O(N + n^2)。在空間複雜度上，我們所提出的方法是最佳的 O(n + m)。不過在時間複雜度上，我們的方法和 Kapoor 與 Ramesh 的方法相比，稍微慢一點。我們的是 O(Nnlogn + n^2 + nm)；Kapoor 與 Ramesh 的是 O(Nn + n^3)。

Let G = (V, E) be a directed graph with vertex set V and edge set E. A directed spanning tree of G rooted at a vertex r is a spanning tree of G having a unique path from r to every other vertex. In this thesis, by using Kapoor and Ramesh’s [8] “edge-exchange” technique, we propose an O(Nnlogn + n^2 + nm) time algorithm for enumerating all spanning trees of a directed graph. The output size of our algorithm is O(N + n^2) that is the same as Kapoor and Ramesh’s algorithm in [8]. Furthermore, although our algorithm is slightly slower than Kapoor and Ramesh’s, the space complexity of our algorithm is O(n + m), which is optimal.

Content.....................................................i
List of Tables.............................................ii
List of Figures...........................................iii
Chapter 1 Introduction......................................1
Chapter 2 Preliminaries.....................................4
2.1 Definitions and Notations............................4
2.2 Algorithm Outline....................................5
2.3 Computation Tree.....................................7
Chapter 3 Kapoor and Ramesh’s Algorithm...................10
Chapter 4 A New Implementation.............................13
4.1 A New Implementation................................13
4.2 Complexity..........................................20
Chapter 5 Concluding Remarks...............................23
References.................................................24

[1] D. Avis and K. Fukuda, “ A Basis Enumeration Algorithm
for Linear Systems with Geometric Applications,” Applied
Mathematics Letters, vol. 4, pp. 39-42, 1991.
[2] D. Avis and K. Fukuda, “ Reverse Search for Enumeration,”
Discrete Applied Mathematics, vol. 65, pp.21-46, 1996.
[3] J. P. Char, “ Generation of Trees, 2 Trees and Storage of
Master Forests,” IEEE Transactions on Circuit Theory, vol.
15, pp. 128-138, 1968.
[4] H. N. Gabow, “ Two Algorithms for Generating Weighted
Spanning Trees in Order,” SIAM Journal on Computing, vol.
6, pp. 139-150, 1977.
[5] S. L. Hakimi and D. G. Green, “ Generation and Realization
of Trees and k-Trees,” IEEE Transactions on Circuit
Theory, vol. 11, pp. 247-255, 1964.
[6] R. Jayakumar, K. Thulasiraman, and M. N. S. Swamy, “
Complexity of Computation of a Spanning Tree Enumerating
Algorithm,” IEEE Transactions on Circuits and Systems,
vol. 31, pp. 853-860, 1984.
[7] S. Kapoor and H. Ramesh, “ Algorithms for Generating All
Spanning Trees of Undirected and Weighted Graph,” SIAM
Journal on Computing, vol. 24, pp. 247-265, 1995.
[8] S. Kapoor and H. Ramesh, “ An Algorithm for Enumerating
All Spanning Trees of a Directed Graph,“ Algorithmica,
vol. 27, pp. 120-130, 2000.
[9] T. Matsui, “ An Algorithm for Finding All the Spanning
Trees in Undirected Graph,” Research Report, Department of
Mathematical Engineering and Information Physics,
University of Tokyo, Tokyo, 1993.
[10] W. Mayeda, Graph Theory, Wiley, New York, 1972.
[11] W. Mayeda and S. Seshu, “ Generation of Trees without
Duplications,” IEEE Transactions on Circuit Theory, vol.
12, pp. 181-185, 1965.
[12] G. J. Minty, “ A Simple Algorithm for Listing All the
Trees of a graph,” IEEE Transactions on Circuit and
Systems, vol. 12, p.120, 1965.
[13] E. W. Myers and H. N. Gabow, “ Finding All Spanning Trees
of Directed and Undirected Graph,” SIAM Journal on
Computing, vol. 7, pp. 280-287, 1978.
[14] R. C. Read and R. E. Tarjan, “ Bounds on Backtrack
Algorithms for Listing Cycles, Paths, and Spanning
Trees,” Networks, vol. 5, pp. 237-252, 1975.
[15] S. Shinoda, “ Finding All Possible Directed Trees of a
Directed Graph,” Electronics and Communications in Japan,
vol. 51-A, pp. 45-47, 1968.
[16] A. Shioura and A. Tamura, “ Efficient Scanning All
Spanning Trees of an Undirected Graph,” Journal of the
Operations Research Society of Japan, vol. 38, pp. 331-
344, 1995.
[17] A. Shioura, A. Tamura, and T. Uno, “ An Optimal Algorithm
for Scanning All Spanning Trees of Undirected Graphs,”
SIAM Journal on Computing, vol. 26, pp. 678-692, 1997.
[18] D. D. Sleator and R. E. Tarjan, “ A Data Structure for
Dynamic Trees,” Journal of Computer and System Sciences,
vol. 26, pp. 362-391, 1983.
[19] R. E. Tarjan, “ Depth-First Search and Linear Graph
Algorithms,” SIAM Journal on Computing, vol. 1, pp.146-
160, 1972.
[20] T. Uno, “ A New Approach for Speeding Up Enumeration
Algorithms,” ISSAC 1998, Lecture Notes in Computer
Science, vol. 1533, Springer-Verlag, pp. 287-296.
[21] T. Uno, “ A New Approach for Speeding Up Enumeration
Algorithm and Its Application for Matroid Bases,” COCOON
1999, Lecture Notes in Computer Science, vol. 1627,
Springer-Verlag, pp. 349-359.