4551
правка
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 22:55, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 53: | Строка 53: | ||
'''Лемма 2 (расширенная лемма о переводе).''' Пусть r > | '''Лемма 2 (расширенная лемма о переводе).''' Пусть <math>r \ge 2 \; </math> фиксировано, пусть <math>\bar{Q}</math> – свойство графов из <math>G^r_{n,p}</math>. Если свойство <math>\hat{Q}</math> выполняется для случайной конфигурации почти наверняка, то соответствующее свойство <math>\bar{Q}</math> почти наверняка выполняется для графа в <math>G^r_{n,p}</math>. | ||
'''Свойство мультисвязности <math>G^r_{n,p}</math>''' | |||
Рассматривается случай вероятности постоянного возникновения пропущенных дуг f, представляющего наихудший случай для сохранения связности. В [ ] показано, что логарифмических степеней достаточно, чтобы гарантировать, что Grn;p с высокой вероятностью остается сильно связным, несмотря на постоянное возникновение пропусков дуг. Подробнее об этом говорит следующая теорема. | Рассматривается случай вероятности постоянного возникновения пропущенных дуг f, представляющего наихудший случай для сохранения связности. В [ ] показано, что логарифмических степеней достаточно, чтобы гарантировать, что Grn;p с высокой вероятностью остается сильно связным, несмотря на постоянное возникновение пропусков дуг. Подробнее об этом говорит следующая теорема. | ||