4551
правка
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 23:15, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 66: | Строка 66: | ||
Тогда G почти наверняка является k-связным, где <math>k = O\left ( \frac{log \; n}{log \; log \; n} \right )</math> | Тогда G почти наверняка является k-связным, где <math>k = O\left ( \frac{log \; n}{log \; log \; n} \right )</math> | ||
В доказательстве теоремы используется граница Черноффа для оценки степеней вершин в | В доказательстве теоремы используется граница Черноффа для оценки степеней вершин в <math>G^r_{n,p}</math> и «схожести» <math>G^r_{n,p}</math> и <math>G_{n,p'} \; </math> (свойства которого известны) для подходящим образом выбранного <math>p' \; </math>. | ||
Для более практичного случая, в котором f = 1 — p = o(1), доказано, что желаемые свойства связности случайных регулярных графов почти сохраняются, несмотря на появление пропущенных ребер. Подробнее: | Для более практичного случая, в котором f = 1 — p = o(1), доказано, что желаемые свойства связности случайных регулярных графов почти сохраняются, несмотря на появление пропущенных ребер. Подробнее: | ||