Content deleted Content added
m border/cellpadding/cellspacing not needed due to wikitable class |
→Further reading: The link should be refreshed. Isn't valid anymore |
||
| (4 intermediate revisions by 4 users not shown) | |||
Line 1:
| last1 = King | first1 = Valerie | author1-link = Valerie King
| title = A Simpler Minimum Spanning Tree Verification 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]]
| |||