4430
правок
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Материал из WEGA
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 23:32, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 83: | Строка 83: | ||
Заметим, что вероятность постоянного возникновения пропущенных дуг существенно изменяет структуру связности регулярного графа в случае низких значений степеней. В частности, использование понятия случайных конфигураций [7] позволяет доказать следующую теорему: | Заметим, что вероятность постоянного возникновения пропущенных дуг существенно изменяет структуру связности регулярного графа в случае низких значений степеней. В частности, использование понятия случайных конфигураций [7] позволяет доказать следующую теорему: | ||
'''Теорема 5.''' Если <math>2 \le r \le \frac{\sqrt{log \; n}}{2}</math> и <math>p = \Theta\ (1) \; </math>, то <math>G^r_{n,p}</math> содержит по меньшей мере одну изолированную вершину с вероятностью не менее <math>1 - n^{- k}, k \ge 2</math>. | |||
Теорема 6. Если f < 1 | |||
На деле скорость потери связности выше, поскольку в [7] показано, что <math>G^r_{n,p}</math> почти наверняка теряет связность даже для <math>r = o(log \; n)</math> и константного значения f. Доказательство последнего утверждения осложняет тот факт, что применение расширенной леммы о переводе невозможно из-за диапазона r. | |||
'''Существование огромного компонента в <math>G^r_{n,p}</math>''' | |||
Поскольку <math>G^r_{n,p}</math> почти наверняка теряет связность при <math>r = o(log \; n)</math> и <math>1 - p = f = \Theta\ (1)</math>, было бы интересно узнать, остается ли связной по крайней мере большая часть сети, представленной <math>G^r_{n,p}</math>; иными словами, является ли наибольший связный компонент <math>G^r_{n,p}</math> действительно большим. В частности, в [7] утверждается следующее: | |||
'''Теорема 6.''' Если <math>f < 1 - \frac{32}{r}</math>, то <math>G^r_{n,p}</math> содержит огромный (размером <math>\Theta\(n) \; </math>) связный компонент для любого <math>r \ge 64 \; </math>. | |||
