4431
правка
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 23:19, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 69: | Строка 69: | ||
Для более практичного случая, в котором f = 1 | Для более практичного случая, в котором <math>f = 1 - p = o(1) \; </math>, доказано, что желаемые свойства связности случайных регулярных графов почти сохраняются, несмотря на появление пропущенных ребер. | ||
'''Теорема 4.''' Пусть <math>r \ge 3 \; </math> и <math>f = 1 - p = O(n^{- \epsilon\ })</math> для <math>\epsilon\ \ge \frac{3}{2r} </math>. Тогда наибольшая часть <math>G^r_{n,p}</math> (иными словами, весь граф за вычетом O(1) вершин) сохраняет связность, и эта связная часть графа (за исключением вершин, которые изначально были соседями потерявшего связность множества размером O(1)) не может быть выделена, если только не удалены более r вершин, с вероятностью, стремящейся к 1, по мере того, как n стремится к <math>+ \infty</math>. | |||
Для доказательства используется расширенная для работы с пропущенными дугами техника, предназначенная для недопущения малых разделителей в случайных регулярных графах. | Для доказательства используется расширенная для работы с пропущенными дугами техника, предназначенная для недопущения малых разделителей в случайных регулярных графах. | ||