計算最短路徑樹的最致命邊

Abstract

在現今的社會裡，鑑於電腦的發展快速及網路的便利性，網路扮演人們生活中舉足輕重的角色。當只有一個伺服器時，我們會使用較低成本的單一樹根最短路徑樹來連結整個網路，而現實生活中網路的鏈結上難免有失效的風險，因此我們若能知道鏈結各自的重要程度，對於較重要的鏈結能加倍注意，如此一來便能減少可能的損失。在此篇論文中，我們提供了尋找最致命邊的演算法。令圖G 為無向圖，每邊有各自的成本，其為一非負實數。假設s 為圖G 的一個頂點，令樹T為樹根在s 的最短路徑樹，我們定義樹T 的總成本為樹根s 到樹上各頂點的成本總和。如果我們從圖G 中移走某個邊，令此時樹根在s 的最短路徑樹為Tˆ ，則最短路徑樹的最致命邊問題是在尋找圖G 中的某個邊，使得移去該邊後，Tˆ 和T的總成本相差最多。在本篇論文中，我們提供了一個O(mα (m,n) + km + knlogn) 的演算法來尋找最短路徑樹的最致命邊，其中n 和m 分別是圖G 的頂點個數及邊數，而k 是樹T 的內部節點個數。

Since the development of computers and the expediency of internet, network plays an important role in the life of human beings. If there is only one computer as the server, then we use a single-source shortest-paths tree to connect the network. Maybe some line of communication is broken. Thus if we know the importance for each line, we may reduce the damage by taking care of more important lines. We de ne G = (V;E;w) to be an undirected graph with n vertices and m edges. And there is an non-negative edge weight function w : E ! R+. Let s 2 V and T be the shortest-paths tree rooted at s. We de ne the cost of T to be the total distance from s to all vertices. If we remove some edge from G, there is a substitute shortest-paths tree ^ T. The most vital edge problem with respect to a shortest-paths tree is to nd an edge in E(G) such that the di erence between the costs of ^ T and T is the largest. In this thesis, we give an algorithm with time complexity O(m (m; n) + km + kn log n), where k is the number of internal nodes of T, and (m; n) is a functional inverse of Ackermann's function.