4430
правок
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Материал из WEGA
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 03:36, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 44: | Строка 44: | ||
Основная ценность этой леммы заключается в том, что при исследовании случайных регулярных графов вместо рассмотрения множества всех случайных регулярных графов можно исследовать только множество конфигураций, работать с которым намного проще. | Основная ценность этой леммы заключается в том, что при исследовании случайных регулярных графов вместо рассмотрения множества всех случайных регулярных графов можно исследовать только множество конфигураций, работать с которым намного проще. | ||
Для обработки пропущенных дуг в [ ] вводится следующее расширение понятия конфигураций: | Для обработки пропущенных дуг в [7] вводится следующее расширение понятия конфигураций: | ||
'''Определение 3 (случайные конфигурации).''' Пусть <math>w = \cup^n_{j=1} w_j</math> – фиксированное множество <math>2m = \sum^n_{j=1} d_j</math> помеченных «вершин», где <math>|w_j| = d_j \; </math>. Пусть F – любая конфигурация множества <math>\varphi\ \;</math> . Взяв каждую дугу из F, удалить ее с вероятностью 1 — p независимым от других образом. Пусть <math>\quad \hat{\phi\ }</math> – новое множество объектов, а <math>\quad \hat{F}</math> – результат эксперимента. <math>\quad \hat{F}</math> будем называть [[случайная конфигурация|случайной конфигурацией]]. | |||
Если ввести для каждой дуги вероятность p, расширение доказательства леммы 1 (поскольку и в Q, и в Q каждая дуга имеет одну и ту же вероятность быть удаленной одинаково независимо от других, в результате чего модифицированные пространства соответствуют свойствам Q и Q*) приводит к следующему расширению случайных конфигураций. | Если ввести для каждой дуги вероятность p, расширение доказательства леммы 1 (поскольку и в Q, и в Q каждая дуга имеет одну и ту же вероятность быть удаленной одинаково независимо от других, в результате чего модифицированные пространства соответствуют свойствам Q и Q*) приводит к следующему расширению случайных конфигураций. | ||
