词条 | Minimum bottleneck spanning tree | ||||||||||
释义 |
In mathematics, a minimum bottleneck spanning tree (MBST) in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible. A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree if the graph does not contain a spanning tree with a smaller bottleneck edge weight.[1] For a directed graph, a similar problem is known as Minimum Bottleneck Spanning Arborescence (MBSA). DefinitionsUndirected graphsIn an undirected graph {{math|G(V, E)}} and a function {{math|w : E → R}}, let {{math|S}} be the set of all spanning trees Ti. Let B(Ti) be the maximum weight edge for any spanning tree Ti. We define subset of minimum bottleneck spanning trees S′ such that for every {{math|Tj ∈ S′}} and {{math|Tk ∈ S}} we have {{math|B(Tj) ≤ B(Tk)}} for all i and k.[2] The graph on the right is an example of MBST, the red edges in the graph form a MBST of {{math|G(V, E)}}. Directed graphsAn arborescence of graph G is a directed tree of G which contains a directed path from a specified node L to each node of a subset V′ of {{math|V \\{{mset|L}}}}. Node L is called the root of arborescence. An arborescence is a spanning arborescence if {{math|1=V′ = V \\{{mset|L}}}}. MBST in this case is a spanning arborescence with the minimum bottleneck edge. An MBST in this case is called a Minimum Bottleneck Spanning Arborescence (MBSA). The graph on the right is an example of MBSA, the red edges in the graph form a MBSA of {{math|G(V, E)}}. PropertiesA MST (or minimum spanning tree) is necessarily a MBST, but a MBST is not necessarily a MST.[3] [4]Camerini's algorithm for undirected graphsCamerini proposed[5] an algorithm used to obtain a minimum bottleneck spanning tree (MBST) in a given undirected, connected, edge-weighted graph in 1978. It half divides edges into two sets. The weights of edges in one set are no more than that in the other. If a spanning tree exists in subgraph composed solely with edges in smaller edges set, it then computes a MBST in the subgraph, a MBST of the subgraph is exactly a MBST of the original graph. If a spanning tree does not exist, it combines each disconnected component into a new super vertex, then computes a MBST in the graph formed by these super vertices and edges in the larger edges set. A forest in each disconnected component is part of a MBST in original graph. Repeat this process until two (super) vertices are left in the graph and a single edge with smallest weight between them is to be added. A MBST is found consisting of all the edges found in previous steps.[6] PseudocodeThe procedure has two input parameters. G is a graph, w is a weights array of all edges in the graph G.[7] 1 '''function''' MBST(graph ''G'', weights ''w'') 2 ''E'' ← the set of edges of ''G'' 3 '''if''' | ''E'' | = 1 '''then''' '''return''' ''E'' '''else''' 4 ''A'' ← half edges in ''E'' whose weights are no less than the median weight 5 ''B'' ← ''E'' - ''A'' 6 ''F'' ← forest of ''G''''B'' 7 '''if''' ''F'' is a spanning tree '''then''' 8 '''return''' MBST(''G''''B'',''w'') 9 '''else''' 10 '''return''' MBST((''G''''A'')''η'', ''w'') ''F'' In the above (GA)η is the subgraph composed of super vertices (by regarding vertices in a disconnected component as one) and edges in A. Running timeThe algorithm is running in O(E) time, where E is the number of edges. This bound is achieved as follows:
ExampleIn the following example green edges are used to form a MBST and dashed red areas indicate super vertices formed during the algorithm steps.
MBSA algorithms for directed graphsThere are two algorithms available for directed graph: Camerini’s algorithm for finding MBSA and another from Gabow and Tarjan.[4] Camerini's algorithm for MBSAFor a directed graph, Camerini’s algorithm focuses on finding the set of edges that would have its maximum cost as the bottleneck cost of the MBSA. This is done by partitioning the set of edges E into two sets A and B and maintaining the set T that is the set in which it is known that GT does not have a spanning arborescence, increasing T by B whenever the maximal arborescence of G(B ∪ T) is not a spanning arborescence of G, otherwise we decrease E by A. The total time complexity is O(E log E).[5][4] Pseudocode1 '''function''' MBSA(''G'', ''w, T'') 2 ''E'' ← the set of edges of ''G;'' 3 '''if''' | ''E - T'' | > 1 '''then''' 4 ''A'' ← UH(E-T); 5 ''B'' ← (''E - T)'' - ''A;'' 6 ''F'' ← BUSH(''G''''BUT''); 7 '''if''' ''F'' is a spanning arborescence of G '''then''' 8 S ← F; MBSA((''G''''BUT''),w,T); 9 '''else''' 10 MBSA(G,''w,TUB'');
Example
Gabow and Tarjan algorithm for MBSAGabow and Tarjan provided a modification of Dijkstra's algorithm for single-source shortest path that produces an MBSA. Their algorithm runs in O(E + V log V) time if Fibonacci heap used.[11] PseudocodeFor a graph ''G(V,E), F'' is a collection of vertices in ''V''. Initially, ''F'' = ''s'' where ''s'' is the starting point of the graph ''G'' and ''c''(''s'') = ∞ 1 '''function''' MBSA-GT(''G'', ''w, T'') 2 Select ''v'' with minimum ''c''(''v'') from ''F''; 3 Delete it from the ''F''; 4 '''for''' ∀ edge(''v,w'') '''do''' 5 '''if''' ''w'' ∉ ''F'' or ∉ Tree '''then''' 6 add ''w'' to ''F;'' 7 ''c''(''w'') = ''c''(''v,w''); 8 ''p''(''w'') = ''v''; 9 '''else''' 10 '''if''' ''w'' ''F'' and ''c(w) > c(v,w)'' '''then''' 11 ''c''(''w'') = ''c''(''v,w''); 12 ''p''(''w'') = ''v'';'' ExampleThe following example shows that how the algorithm works. Another approach proposed by Tarjan and Gabow with bound of {{math|O(E log* V)}} for sparse graphs, in which it is very similar to Camerini’s algorithm for MBSA, but rather than partitioning the set of edges into two sets per each iteration, {{math|1=K(i)}} was introduced in which i is the number of splits that has taken place or in other words the iteration number, and {{math|1=K(i)}} is an increasing function that denotes the number of partitioned sets that one should have per iteration. {{math|1=K(i) = 2k(i − 1)}} with {{math|1=k(1) = 2}}. The algorithm finds {{math|1=λ*}} in which it is the value of the bottleneck edge in any MBSA. After {{math|λ*}} is found any spanning arborescence in {{math|1=G(λ*)}} is an MBSA in which {{math|G(λ*)}} is the graph where all its edge’s costs are {{math|1=≤ λ*}}.[4][8] References1. ^Everything about Bottleneck Spanning Tree 2. ^{{citation | last1 = Murali| first1 =T. M. | title = Applications of Minimum Spanning Trees | url = http://courses.cs.vt.edu/~cs5114/spring2009/lectures/lecture08-mst-applications.pdf | year = 2009}} 3. ^{{citation | title = in question 3 you have a proof for this claim | url =https://stanford.edu/~rezab/discrete/Midterm/midterm2016_soln.pdf | }} 4. ^1 2 3 {{citation | last1 = Traboulsi | first1 =Ahmad | title = Bottleneck Spanning Trees | url = http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/14Seminars/BST-Report.pdf | year = 2014}} 5. ^1 {{citation|last1=Camerini|first1=P.M.|title=The min-max spanning tree problem and some extensions|journal=Information Processing Letters|year=1978|volume=7|issue=1|doi=10.1016/0020-0190(78)90030-3|pages=10}} 6. ^{{citation | last1 = Traboulsi | first1 =Ahmad | title = Bottleneck Spanning Trees | url = http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/14Seminars/BST-Report.pdf | year = 2014}} 7. ^{{citation | last1 = Cui| first1 =Yuxiang| title = Minimum Bottleneck Spanning Tree | url = http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Talks/MBST/slides.pdf | year = 2013}} 8. ^1 {{cite journal|last1=Gabow|first1=Harold N|last2=Tarjan|first2=Robert E|title=Algorithms for two bottleneck optimization problems|journal=Journal of Algorithms|volume=9|issue=3|year=1988|pages=411–417|issn=0196-6774|doi=10.1016/0196-6774(88)90031-4|url=http://www.cs.princeton.edu/research/techreps/TR-104-87}} 2 : Graph algorithms|Spanning tree |
||||||||||
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。