Content deleted Content added
→Performance: MOS:HEAD |
→Further reading: The link should be refreshed. Isn't valid anymore |
||
| (6 intermediate revisions by 6 users not shown) | |||
Line 1:
| last1 = King | first1 = Valerie | author1-link = Valerie King
| title = A Simpler Minimum Spanning Tree Verification Algorithm
Line 28:
Example execution of a Borůvka step
{|
! Image !! Description
|-
Line 48:
===F-heavy and F-light edges===
In each iteration the algorithm removes edges with particular properties that exclude them from the [[minimum spanning tree]]. These are called ''F-heavy edges'' and are defined as follows. Let ''F'' be a forest on the [[Graph (discrete mathematics)|graph]] ''H''. An F-heavy edge is an edge ''e'' connecting vertices ''u'',''v'' whose weight is strictly greater than the weight of the heaviest edge on the path from ''u'' to ''v'' in ''F''. (If a path does not exist in ''F'' it is considered to have infinite weight). Any edge that is not F-heavy is ''F-light''. If ''
==Algorithm==
Line 66:
===Random sampling lemma===
'''Lemma'''- Let ''H'' be a subgraph of ''G'' formed by including each edge of ''G'' independently with probability ''p'' and let ''F'' be the minimum spanning forest of ''H''. The [[Expected value|expected number]] of '''[[#F-heavy and F-light Edges|F-light]]''' edges in ''G'' is at most ''n/p'' where ''n'' is the number of vertices in ''G''
To prove the lemma examine the edges of ''G'' as they are being added to ''H''. The number of [[#F-heavy and F-light Edges|F-light]] edges in ''G'' is independent of the order in which the edges of ''H'' are selected since the minimum spanning forest of ''H'' is the same for all selection orders. For the sake of the proof consider selecting edges for ''H'' by taking the edges of ''G'' one at a time in order of edge weight from lightest to heaviest. Let ''e'' be the current edge being considered. If the endpoints of ''e'' are in two disconnected components of ''H'' then ''e'' is the lightest edge connecting those components and if it is added to ''H'' it will be in ''F'' by the [[Minimum_spanning_tree#Cut_property|cut property]]. This also means ''e'' is [[#F-heavy and F-light Edges|F-light]] regardless of whether or not it is added to ''H'' since only heavier edges are subsequently considered. If both endpoints of ''e'' are in the same component of ''H'' then it is (and always will be) F-heavy by the [[Minimum_spanning_tree#Cycle_property|cycle property]]. Edge ''e'' is then added to ''H'' with probability ''p''.
Line 90:
==References==
{{Reflist}}
[[Category:Randomized algorithms]]
| |||