




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、1Minimum Spanning Tree 2Flight Path Problem3Flight Path Problem Consider the graph representing the airline connections between seven cities.abcdefg65916131215837the least flight pathsthe least cost Flight Path ProblemMinimum Spanning Tree4Minimum Spanning Tree Introduction Problem Definition Boruvk
2、as algorithm Conclusion5Introduction The minimum spanning tree problem is one of the oldest and most basic graph problems in theoretical computer science. Its history dates back to Boruvkas algorithm in 1926 and till to day it is a extensively researched problem with new breakthroughs only recently.
3、 6Problem Definition All the graphs in this report are finite,simple,and undirected. We denote by n the number of vertices, m the number of edges in a graph G=(V,E). Our graphs are weighted,w(e)denoting the distinct weight of the edge e.7Problem Definition A spanning tree in G is an acyclic subgraph
4、 of G that includes every vertex of G and is connected; every spanning tree has exactly n-1 edges. The weight of a tree is defined to be the sum of the weights of its edges. A minimum spanning tree (MST) is a spanning tree of minimum weight.8MSTP: The Minimal Spanning Tree problem (MSTP)is: Input: A
5、 weighted graphG=(v,e ,w). Output: The Unique spanning tree T that minimizes .)(ewTe9MSF When the input graph G is not connected, a spanning tree does not exist and we generalize the notion of a minimum spanning tree to that of a minimum spanning forest (MSF). A spanning forest is a forest whose tre
6、es are spanning trees for the connected components of the graph G.10MSF So when G is not connected we find the minimal spanning forest MSF: A set of trees,one in each of the connected component of G,each tree being a minimal spanning tree of the graph induced by the component.A spanning forest is a
7、spanning tree if and only if the graph is connected. 11MSTa spanning tree: ahbcigfedthe weights of this tree: 8+11+8+2+6+2+10+9=56.minimal spanning tree: abcifghdethe weights of MST: 4+8+7+2+4+9+2+1=3756.12MST2nn Given an edge-weighted graph, this problem calls for finding a subtree spanning all the
8、 vertices, whose total weight is minimal. For a n-degree complete graph, there are spanning trees . Then the central open question is: Does there exist a linear time deterministic algorithm that finds the minimal spanning tree? 13MSTP The MSTP is one of the best-studied problems in combinatorial opt
9、imization. A variety of algorithms have been developed for this problem, most of which are based on a greedy strategy and run in near-linear O(m log n) time, e.g.,Boruvkas algorithm , Kruskals algorithm , Prims algorithm.14Boruvkas algorithm The first MST algorithm was devised by Boruvka ,the algori
10、thm is based on the greedy strategy. The basic step in Boruvkas algorithm is the heart of many MST algorithms till to day. 15Boruvkas algorithmV we start with one-vertex trees; for each vertex v, we look for an edge(vw) of minimum weight among all edges outgoing from v create small trees by includin
11、g these edges. Then, we look for edges of minimal weight that can connect the resulting tree to larger trees. The process is finished when one tree is created.16The process of Boruvkas algorithm abcdefgabcdefgabcdefg6591613121583756783122.For this graph, out of seven one-vertex ,two trees are create
12、d because, for vertices a and c,edge( ac) is chosen, for vertex b, edge(ab) is chosen, for vertex d, edge(df) is chosen, for vertex e, edge(eg) is chosen, and for vertices f and g, edge(fg) is chosen. 3.for the tree(abc) and the tree(defg), edge(cf)is selected, since it is the shortest edge that con
13、nects these two trees, resulting in one spanning tree.3875617pseudocode: BoruvkaAlgorithnm(weighted connected undirected graph) make each vertex the root of a one-node tree; While there is more than one tree For each tree t e=minimum weight edge(vu) where v is included in t and u is not; create a tr
14、ee by combining t and the tree that includes u if such a tree does not exist yet;18Boruvkas algorithm Does this algorithm run in a linear time? Boruvkas algorithm thus reduces the MST problem in an n-vertex graph with m edges to the MST problem in an (n/2)-vertex graph with at most m edges. The time required for the reduction is only O(m+n). It follows that t
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2031年中國硫化新藍(lán)行業(yè)投資前景及策略咨詢研究報告
- 2025-2030年中國NVS市場需求預(yù)測與發(fā)展規(guī)劃研究報告
- 廣東省東莞市橫瀝莞盛校2024年中考猜題數(shù)學(xué)試卷含解析
- 2025班組安全培訓(xùn)考試試題附完整答案(奪冠系列)
- 2024-2025管理人員崗前安全培訓(xùn)考試試題附參考答案(輕巧奪冠)
- 2025生產(chǎn)經(jīng)營負(fù)責(zé)人安全培訓(xùn)考試試題【歷年真題】
- 2025部門安全培訓(xùn)考試試題答案AB卷
- 2024-2025公司廠級安全培訓(xùn)考試試題附完整答案【歷年真題】
- 2024-2025公司安全管理員安全培訓(xùn)考試試題及參考答案【考試直接用】
- 2025新員工入職安全培訓(xùn)考試試題綜合題
- 中小學(xué)教師資格證面試課件講義
- 全國初中英語優(yōu)質(zhì)課大賽一等獎《八年級Unit 6An old man》說課課件
- 西班牙文化概況
- 云南省飲用水生產(chǎn)企業(yè)名錄534家
- 湖北地區(qū)醫(yī)院詳細(xì)名單一覽表
- 麥肯錫入職培訓(xùn)第一課:讓職場新人一生受用的邏輯思考力新員工培訓(xùn)教材
- 蘇霍姆林斯基教育思想-PPT課件
- 脊髓損傷康復(fù)評定治療PPT課件
- 啤酒貼標(biāo)機畢業(yè)設(shè)計論文
- 金屬壓鑄機的plc控制
- 進(jìn)制轉(zhuǎn)換(課堂PPT)
評論
0/150
提交評論