Изменения

Перейти к: навигация, поиск

Случайные графы

8 байт добавлено, 16:10, 4 декабря 2019
м
Связность графа
<tex>X_i = \sum\limits_{a_1,a_2, \dots , a_i} X_{a_1,a_2, \dots , a_i}</tex>
<tex>EX_i E[X_i] = \sum\limits_{a_1,a_2, \dots , a_i} EX_E[X_{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 E[X] \sum\limits_{i = 1}^{n - 1} EX_i E[X_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>).
31
правка

Навигация