4817
правок
Независимые множества в случайных графах пересечений: различия между версиями
Перейти к навигации
Перейти к поиску
Независимые множества в случайных графах пересечений (посмотреть исходный код)
Версия от 07:21, 26 февраля 2020
, 26 февраля 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
'''Теорема 1. Обозначим за <math>X^{(k)}</math> число независимых множеств размера k в случайном графе пересечений <math>G(n, m,\overrightarrow{p})</math>, где <math>\overrightarrow{p} = [p_1, p_2, ..., p_m]</math>. Тогда''' | '''Теорема 1. Обозначим за <math>X^{(k)}</math> число независимых множеств размера k в случайном графе пересечений <math>G(n, m,\overrightarrow{p})</math>, где <math>\overrightarrow{p} = [p_1, p_2, ..., p_m]</math>. Тогда''' | ||
<math>E[X^{(k)}] = \binom{n}{k} \prod_{i=1}^m ((1 - p_i)^k + kp_i (1 - p_i)^{k - 1}).</math> | <math>E \Big[ X^{(k)} \Big] = \binom{n}{k} \prod_{i=1}^m \Big( (1 - p_i)^k + kp_i (1 - p_i)^{k - 1} \Big).</math> | ||
Теорема 2. Обозначим за X(k) число независимых множеств размера k в случайном графе пересечений G(n | '''Теорема 2. Обозначим за <math>X^{(k)}</math> число независимых множеств размера k в случайном графе пересечений <math>G(n, m,\overrightarrow{p})</math>, где <math>\overrightarrow{p} = [p_1, p_2, ..., p_m]</math>. Тогда''' | ||
<math>Var \big( X^{(k)} \big) = \sum_{s=1}^k \binom{n}{2k - s} \binom{2k - s}{s} \Big( \gamma(k, s) \frac{E[x^{(k)}]}{\binom{n}{k}} - \frac{E^2 [X^{(k)}]}{\binom{n}{k}^2} \Big)</math>, где E [X^] – среднее число независимых множеств размера k, а m Y(k, s)= }~ | |||