89
правок
Изменения
Нет описания правки
<tex>P(Z_n = 0) = P(Z_n \leqslant 0) = P(EZ_n - Z_n \geqslant EZ_n) \leqslant P(|EZ_n - Z_n| \geqslant EZ_n) \leqslant \dfrac{DZ_n}{(EZ_n)^2} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
== Графы имеющие диаметр два ==
{{Теорема
|statement=Пусть рассматривается свойство графа иметь диаметр два. Тогда <tex>p = \sqrt{2} \sqrt{\dfrac{\ln n}{n}}</tex> {{---}} порог.
|proof=
Назовем вершины <tex>u</tex> и <tex>v</tex> плохой парой, если <tex>dist(u, v) > 2</tex>. <tex>B_{i, j}</tex> {{---}} индикаторная величина, равная <tex>1</tex>, если <tex>i</tex> и <tex>j</tex> плохая пара.
<tex>N_z = \sum\limits_{i, j} B_{i,j}</tex>
<tex>P(B_{i, j}) = (1 - p)(1 - p^2)^{n - 2}</tex>
Сначала докажем, что при <tex>c > sqrt{2}</tex>, граф а.п.н не имеет диаметр два. Для этого оценим матожидание <tex>N_z</tex>.
<tex>EN_z = C_n^2(1 - p)(1 - p^2)^{n - 2} \approx \dfrac{n^2}{2}(1 - c\sqrt{\dfrac{\ln n}{n}})(1 - \dfrac{c^2\ln n}{n})^{n - 2} \leqslant \dfrac{n^2}{2}e^{-c^2\ln n} = \dfrac{n^{2 - c^2}}{2}</tex>
При <tex>c > \sqrt{2}</tex> последнее выражение стремится к <tex>0</tex>, по [[#th1 | первой теореме ]] граф а.п.н. не имеет диаметр два.
Рассмотрим <tex>c < \sqrt{2}</tex>:
<tex>EN_z^2 = E(\sum B_{i, j})^2 = E\sum B_{i,j}^2 + E\sum B_{i,j}B_{k,l} = EN_z + \sum EB_{i,j}B_{k,l}</tex>
Рассмотрим сумму <tex>\sum EB_{i,j}B_{k,l}</tex>:
Если <tex>i</tex>, <tex>j</tex>, <tex>k</tex> и <tex>k</tex> различны, то <tex>EB_{i,j}B_{k,l} \leqslant (1 - p^2)^{2(n - 4)} \leqslant n^{-2c^2}(1 + o(1))</tex>.
<tex>\sum EB_{i,j}B_{k,l} \leqslant n^{4 - 2c^2}(1 + o(1))</tex>
<tex>EB_{i,j}B_{i,l} = (1 - p + p(1 - p)^2)^{n - 3} \approx (1 - 2p^2)^{n - 3} = (1 - 2c^2\dfrac{\ln n}{n})^{n - 3} \approx e^{-2c^2 \ln n} = n^{-2c^2}</tex>
<tex>\sum EB_{i,j}B_{i,l} \leqslant n^{3 - 2c}</tex>
В итоге: <tex>EN_z^2 \leqslant n^{2 - c^2} + n^{4 - 2c^2} + n^{3 - 2c^2}. Из этого следует, что <tex>EN_z \leqslant (EN_z)^2(1 + o(1))</tex>, а значит граф а.п.н имеет диаметр два при <tex>c > \sqrt{2}</tex>.
}}
== См. также ==
