趙坤茂臺灣大學：資訊工程學研究所蕭志亘Hsiao, Chih-YuanChih-YuanHsiao2007-11-262018-07-052007-11-262018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/53717在網路的設計上，樹狀結構是建構成本比較小的，但若某一個連結斷掉可能會造成整個網路失效，此時如何快速地找到可補救的連結就相當重要；我們在此篇論文中提出幾個有效率的演算法來為每個樹邊找出可替代的邊。令樹T是圖G 的生成樹，而S V(G)是起始點的集合，T的路由成本是所有的起始點到所有點的距離總和。對一個T上的邊e而言，其替代邊f 是一個可將e取代的邊並取代後所形成的新樹擁有最小的路由成本。給定一個無向圖G和G 的一個生成樹T，本篇論文探討如何快速地為T中的每一個邊都找到替代邊，在起始點的個數為2的情況下，我們提出了一個時間複雜度為O(mlogn+n2)的演算法；而在起始點個數大於2的情況下，我們提出另一個演算法在O(mn)的時間複雜度下解掉替代邊的問題，其中m和n分別是邊和點的個數。Let T be a spanning tree of a graph G and S V(G) be a set of sources. The routing cost of T is the total distance from all sources to all vertices. For an edge e of T, the swap edge of e is the edge f minimizing the routing cost of the tree formed by replacing e with f. Given an undirected graph G and a spanning tree T of G, we investigate the problem of finding the swap edge for every tree edge. In this thesis, we propose an O(mlogn+n2)-time algorithm for the case of two sources and an algorithm with time complexity O(mn) for the case of more than two sources, in which m and n are the numbers of edges and vertices of G, respectively.1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Preliminaries 3 2.1 Notations and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 SERT in the Single-Source Case . . . . . . . . . . . . . . . . . . . . . . . 4 3 SERT in the Two-Sources Case 7 3.1 Introduction of the Two-Sources case . . . . . . . . . . . . . . . . . . . . 7 3.2 Edges not in the Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Edges in the Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.4 Algorithm and Time Complexity . . . . . . . . . . . . . . . . . . . . . . 13 4 SERT in the Multiple-Sources Case 17 4.1 Introduction of the Multiple-Sources Case . . . . . . . . . . . . . . . . . 17 4.2 Computing the Routing Cost by Traversing the Subtree . . . . . . . . . . 17 4.3 Algorithm and Time Complexity . . . . . . . . . . . . . . . . . . . . . . 20 5 Conclusions and Future Works 23 5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.2 The Vital Edge Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.3 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25385288 bytesapplication/pdfen-US路由樹替代邊生成樹spanning treerouting treeswap edgethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53717/1/ntu-94-R92922057-1.pdf