Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
Если ввести для каждой дуги вероятность p, расширение доказательства леммы 1 (поскольку и в Q, и в Q каждая дуга имеет одну и ту же вероятность быть удаленной одинаково независимо от других, в результате чего модифицированные пространства соответствуют свойствам Q и Q*) приводит к следующему расширению случайных конфигураций. | Если ввести для каждой дуги вероятность p, расширение доказательства леммы 1 (поскольку и в <math>\bar{Q}</math>, и в <math>\hat{Q}</math> каждая дуга имеет одну и ту же вероятность быть удаленной одинаково независимо от других, в результате чего модифицированные пространства соответствуют свойствам <math>Q \; </math> и <math>Q^* \;</math>) приводит к следующему расширению случайных конфигураций. | ||
Лемма 2 (расширенная лемма о переводе). Пусть r > 2 фиксировано, пусть Q – свойство графов из Grn p. Если свойство Q выполняется для случайной конфигурации почти наверняка, то соответствующее свойство Q почти наверняка выполняется для графа в Grn p. | |||
'''Лемма 2 (расширенная лемма о переводе).''' Пусть r > 2 фиксировано, пусть Q – свойство графов из Grn p. Если свойство Q выполняется для случайной конфигурации почти наверняка, то соответствующее свойство Q почти наверняка выполняется для графа в Grn p. | |||
Свойство мультисвязности Grn | Свойство мультисвязности Grn | ||