4551
правка
Независимые множества в случайных графах пересечений: различия между версиями
Перейти к навигации
Перейти к поиску
Независимые множества в случайных графах пересечений (посмотреть исходный код)
Версия от 21:42, 13 мая 2020
, 13 мая 2020→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
== Основные результаты == | == Основные результаты == | ||
Следующие теоремы рассматривают существование независимых множеств вершин мощности k в случайных графах пересечений. Доказательство теоремы 1 использует факт линейности математического ожидания суммы случайных переменных. | Следующие теоремы рассматривают существование независимых множеств вершин мощности k в случайных графах пересечений общего вида. Доказательство теоремы 1 использует факт линейности математического ожидания суммы случайных переменных. | ||
| Строка 32: | Строка 32: | ||
'''где <math>E[X^{(k)}]</math> – среднее число независимых множеств размера k,''' | '''где <math>E[X^{(k)}]</math> – среднее число независимых множеств размера k,''' | ||
'''а <math>\gamma(k, s) = \prod_{i=1}^m \Big( (1 - p_i)^{k - s} + (k - s)p_i (1 - p_i)^{k - s - 1} | '''а <math>\gamma(k, s) = \prod_{i=1}^m \Big( (1 - p_i)^{k - s} + (k - s)p_i (1 - p_i)^{k - s - 1} \Big( 1 - \frac{sp_i}{1 + (k - 1) p_i} \Big) \Big).</math>''' | ||
Для доказательства теоремы 2 вначале запишем дисперсию в виде суммы ковариаций, а затем применим технику сжатия вершин, выполняющую слияние нескольких вершин в одну супер-вершину со схожим вероятностным поведением, для вычисления ковариаций. При помощи метода моментов второго порядка | Для доказательства теоремы 2 вначале запишем дисперсию в виде суммы ковариаций, а затем применим технику сжатия вершин, выполняющую слияние нескольких вершин в одну супер-вершину со схожим вероятностным поведением, для вычисления ковариаций. При помощи метода моментов второго порядка [1] можно вычислить порог для существования независимых множеств размера k. | ||