4551
правка
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 23:11, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
Рассматривается случай вероятности постоянного возникновения пропущенных дуг f, представляющего наихудший случай для сохранения связности. В [ ] показано, что логарифмических степеней достаточно, чтобы гарантировать, что | Рассматривается случай вероятности постоянного возникновения пропущенных дуг f, представляющего наихудший случай для сохранения связности. В [7] показано, что логарифмических степеней достаточно, чтобы гарантировать, что <math>G^r_{n,p}</math> с высокой вероятностью остается сильно связным, несмотря на постоянное возникновение пропусков дуг. Подробнее об этом говорит следующая теорема. | ||
Тогда G почти наверняка является k-связным, где | '''Теорема 3.''' Пусть G – экземпляр <math>G^r_{n,p}</math>, где <math>p = \Theta(1) \; </math> и <math>r \ge \alpha\ log n</math>, где <math>\alpha > 0 \; </math> – подходящая константа. | ||
Тогда G почти наверняка является k-связным, где <math>k = O\left ( \frac{log \; n}{log \; log \; n} \right )</math> | |||
В доказательстве теоремы используется граница Черноффа для оценки степеней вершин в Grn p и «схожести» Gnr; p и Gn;p0 (свойства которого известны) для подходящим образом выбранного p0. | В доказательстве теоремы используется граница Черноффа для оценки степеней вершин в Grn p и «схожести» Gnr; p и Gn;p0 (свойства которого известны) для подходящим образом выбранного p0. | ||