|
example of one execution of the algorithm. After execution, we get a cut of size 3.
'''{{math theorem|name=Lemma 1''': |1=Let ''k'' be the min cut size, and let {{math|1=''C'' = {{mset|''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>''k''</sub>}}}} be the min cut. If, during iteration ''i'', no edge {{math|''e'' ∈ ''C''}} is selected for contraction, then {{math|1=''C''<sub>''i''</sub> = ''C''}}.}}
'''Proof''':{{math proof|1=If ''G'' is not connected, then ''G'' can be partitioned into ''L'' and ''R'' without any edge between them. So the min cut in a disconnected graph is 0. Now, assume ''G'' is connected. Let {{math|1=''V''=''L''∪''R''}} be the partition of ''V'' induced by <span class="texhtml">''C'' : ''C'' = { {''u'',''v''} ∈ ''E'' : ''u'' ∈ ''L'',''v'' ∈ ''R'' }</span> (well-defined since ''G'' is connected). Consider an edge {''u'',''v''} of ''C''. Initially, ''u'',''v'' are distinct vertices. ''As long as we pick an edge {{tmath|f \neq e}}, {{mvar|u}} and {{mvar|v}} do not get merged.'' Thus, at the end of the algorithm, we have two compound nodes covering the entire graph, one consisting of the vertices of ''L'' and the other consisting of the vertices of ''R''. As in figure 2, the size of min cut is 1, and ''C'' = {(''A'',''B'')}. If we don't select (''A'',''B'') for contraction, we can get the min cut.}}
'''{{math theorem|name=Lemma 2''': |1=If ''G'' is a multigraph with ''p'' vertices and whose min cut has size ''k'', then ''G'' has at least ''pk''/2 edges.}}
{{math proof|1=
'''Proof''':
Because the min cut is ''k'', every vertex ''v'' must satisfy degree(''v'') ≥ ''k''. Therefore, the sum of the degree is at least ''pk''. But it is well known that the sum of vertex degrees equals 2{{abs|''E''|}}. The lemma follows.
}}
'''==== Analysis of algorithm''' ====
The probability that the algorithm succeeds is 1 − the probability that all attempts fail. By independence, the probability that all attempts fail is
|
