Изменения

Дан связный неориентированный граф <tex> G = (V, E) </tex>, с ребрами веса <tex> w_e </tex>. Требуется найти минимальное остовное дерево <tex>T = (V, E')</tex> минимального веса <tex> w(T) = \sum_{e \in E'} w_e </tex>.

'''Утверждение 1:'''

<tex> (\frac {1} {1 + \frac{1}{n}})^n = (\frac {1} {\frac{n + 1}{n}})^n = (\frac {n} {n+1})^n \stackrel{ _{m = n + 1}}{=}

(1 - \frac{1}{m}) ^ {m-1}</tex>

'''Утверждение 2:'''

2) <tex>b \leq a \Rightarrow \frac{a}{b} \leq \frac{a - 1} {b - 1}, a,b > 1 \Rightarrow (1) </tex>

'''Утверждение 3:'''

<tex> (1 - \frac{1}{n})^{n - k} \geq \frac{1}{e} </tex> по Утверждению 1, отсюда следует Утверждение 3.

'''Утверждение 4:'''

<tex> C_n^k (\frac{1}{n})^k(1 - \frac{1}{n})^{n - k}

\geq \frac{n^k}{k^k} \frac{1}{e n^k} = \frac{1}{e k^k}</tex> по Утверждениям 1 и 4.

'''Утверждение 5 (Лемма об ожидании):'''

Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание наступления этого события

'''Доказательство:'''

<tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex>

=== Алгоритм RMHC ===