4430
правок
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Материал из WEGA
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 23:23, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 75: | Строка 75: | ||
Для доказательства используется расширенная для работы с пропущенными дугами техника, предназначенная для недопущения малых разделителей в случайных регулярных графах. | Для доказательства используется расширенная для работы с пропущенными дугами техника, предназначенная для недопущения малых разделителей в случайных регулярных графах. | ||
'''<math>G^r_{n,p}</math> теряет связность''' | |||
Заметим, что вероятность постоянного возникновения пропущенных дуг существенно изменяет структуру связности регулярного графа в случае низких значений степеней. В частности, использование понятия случайных конфигураций [7] позволяет доказать следующую теорему: | |||
Заметим, что вероятность постоянного возникновения пропущенных дуг существенно изменяет структуру связности регулярного графа в случае низких значений степеней. В частности, использование понятия случайных конфигураций [ ] позволяет доказать следующую теорему: | |||
Теорема 5. Если 2 < r < - r - 2 и p = 0(1), то Grn p содержит по меньшей мере одну изолированную вершину с вероятностью не менее l-n~k,k>2. | '''Теорема 5.''' Если 2 < r < - r - 2 и p = 0(1), то Grn p содержит по меньшей мере одну изолированную вершину с вероятностью не менее l-n~k,k>2. | ||
На деле скорость потери связности выше, поскольку в [7] показано, что Grn p почти наверняка теряет связность даже для r = o(log n) и константного значения f. Доказательство последнего утверждения осложняет тот факт, что применение расширенной леммы о переводе невозможно из-за диапазона r. | На деле скорость потери связности выше, поскольку в [7] показано, что Grn p почти наверняка теряет связность даже для r = o(log n) и константного значения f. Доказательство последнего утверждения осложняет тот факт, что применение расширенной леммы о переводе невозможно из-за диапазона r. | ||
| Строка 92: | Строка 90: | ||
Теорема 6. Если f < 1 — ^, то Grn p содержит огромный (размером 0{n)) связный компонент для любого r > 64 | Теорема 6. Если f < 1 — ^, то Grn p содержит огромный (размером 0{n)) связный компонент для любого r > 64 | ||
с вероятностью не менее 1 — O(log n)/(na/3), где a > 0 – константа, которую требуется выбрать. | |||
Для доказательства существования компоненты необходимо вначале доказать существование (с высокой вероятностью) достаточно длинного пути (логарифмической длины) в качестве основы для процесса поиска базисного возможного решения, начинающегося с вершин того пути, на основе которого создается компонент. В процессе довольно сложного доказательства используются соображения занятости (столбики диаграмм соответствуют вершинам графов, а шары – дугам); однако упоминаемые в ходе него случайные переменные не являются независимыми, и для использования границ Черноффа-Хеффдинга для концентрации необходимо вначале доказать, что эти случайные переменные, не будучи независимыми, являются отрицательно связанными. Далее при оценке успешности процесса поиска базисного возможного решения используется более точный и детальный алгоритм «анализа в среднем». | |||
Построение пути и процесса поиска базисного возможного решения могут в совокупности рассматриваться как алгоритм, который (в случае, если не найдено пропусков) позволяет найти огромный связный компонент. Этот алгоритм весьма эффективен, что иллюстрирует следующая теорема. | |||
Теорема 7. Огромный компонент Gnr; p может быть построен за время O(n log n) с вероятностью не менее 1 — O(log2 n)/(nal3), где a > 0 – константа, которую можно выбрать. | |||
== Применение == | == Применение == | ||
