89
правок
Изменения
→Связность графа
|id=lemma1
|statement=Если <tex>c \geqslant 3</tex>, <tex>n \geqslant 100</tex>, <tex>p = \dfrac{c\ln n}{n}</tex>. Тогда <tex>P(G - связен) \rightarrow 1</tex>.
|proof=
Пусть <tex>X</tex> {{---}} индикаторная величина, равная <tex>0</tex>, если <tex>G</tex> связен, и <tex>k</tex>, если <tex>G</tex> содержит <tex>k</tex> компонент связности.
<tex>X_i</tex> {{---}} число компонент связности размера <tex>i</tex>.
<tex>X_{a_1,a_2, \dots , a_i} = 1</tex>, если <tex>a_1,a_2, \dots , a_i</tex> {{---}} компонента связности.
<tex>X_i = \sum\limits_{a_1,a_2, \dots , a_i} X_{a_1,a_2, \dots , a_i}</tex>
<tex>EX_i = \sum\limits_{a_1,a_2, \dots , a_i} EX_{a_1,a_2, \dots , a_i} = C_n^iEX_{1, 2, \dots, i} = C_n^i P(1, 2, \dots, i - комп.связности) \leqslant C_n^i (1 - p)^{i(n - i)}</tex>.
<tex>EX \sum\limits_{i = 1}^{n - 1} EX_i \leqslant \sum\limits_{i = 1}^{n - 1} C_n^i(1 - p)^{i(n - i)}</tex>
Последняя сумма симметрична (слагаемые при <tex>i = k</tex> и <tex>i = n - k</tex> равны), кроме того слагаемое при <tex>i = 1</tex> {{---}} наибольшее (для доказательства достаточно рассмотреть отношения слагаемых при <tex>i \leqslant \dfrac{n}{8}</tex> и <tex>\dfrac{n}{8} < i \leqslant \dfrac{n}{2}</tex>).
Оценим сверху первое слагаемое <tex>n(1 - p)^{n - 1}</tex>:
<tex>n(1 - p)^{n - 1} \leqslant ne^{-p(n - 1)} \leqslant ne^{\frac{-3 (n - 1) \ln n}{n}}</tex>
<tex>n \geqslant 100</tex>, поэтому <tex>\dfrac{n - 1}{n} > 0.9</tex>.
<tex>ne^{\frac{-3 (n - 1) \ln n}{n}} < e^{-2.7\ln n} = \dfrac{1}{n^{2.7}}</tex>
<tex>\sum\limits_{i = 1}^{n - 1} C_n^i(1 - p)^{i(n - i)} \leqslant \sum\limits_{i = 1}^{n - 1}\dfrac{1}{n^{2.7}} < \dfrac{n}{n^{2.7}} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>
}}
