4551
правка
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 03:31, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
Пусть | Пусть <math>\varphi\ \; </math> – множество всех конфигураций F, а <math>G^r_n</math> – множество всех регулярных графов. Учитывая свойство <math>Q \subseteq G^r_n</math>, положим <math>Q^* \subseteq \phi\ </math>, такое, что <math>Q^* \cap \theta\ ^{-1} (G^r_n) = \theta\ ^{-1}(Q)</math>. В результате оценки вероятности возможных циклов длины 1 (петля) и 2 (цикл) между парами <math>w_i, w_j \; </math> в <math>\theta\ (F)</math> получается следующая лемма. | ||
'''Лемма 1 (Боллобас, [2]).''' Если <math>r \ge 2 \; </math> фиксировано, а свойство <math>Q^* \; </math> выполняется для конфигурации почти наверняка, то свойство Q почти наверняка выполняется для r–регулярного графа. | |||
Основная ценность этой леммы заключается в том, что при исследовании случайных регулярных графов вместо рассмотрения множества всех случайных регулярных графов можно исследовать только множество конфигураций, работать с которым намного проще. | Основная ценность этой леммы заключается в том, что при исследовании случайных регулярных графов вместо рассмотрения множества всех случайных регулярных графов можно исследовать только множество конфигураций, работать с которым намного проще. | ||