4430
правок
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Материал из WEGA
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 23:41, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 96: | Строка 96: | ||
'''Теорема 6.''' Если <math>f < 1 - \frac{32}{r}</math>, то <math>G^r_{n,p}</math> содержит огромный (размером <math>\Theta\ (n) \; </math>) связный компонент для любого <math>r \ge 64 \; </math>. | '''Теорема 6.''' Если <math>f < 1 - \frac{32}{r}</math>, то <math>G^r_{n,p}</math> содержит огромный (размером <math>\Theta\ (n) \; </math>) связный компонент для любого <math>r \ge 64 \; </math> с вероятностью не менее <math>1 - O(log^2 n)/(n^{\alpha\ /3})</math>, где <math>\alpha\ > 0</math> – константа, которую требуется выбрать. | ||
Теорема 7. Огромный компонент | Для доказательства существования компоненты необходимо вначале доказать существование (с высокой вероятностью) достаточно длинного пути (логарифмической длины) в качестве основы для процесса обхода в ширину, начинающегося с вершин того пути, на основе которого создается компонент. В процессе довольно сложного доказательства используются соображения занятости (столбики диаграмм соответствуют вершинам графов, а круги – дугам); однако упоминаемые в ходе него случайные переменные не являются независимыми, и для использования границ Черноффа-Хеффдинга для концентрации необходимо вначале доказать, что эти случайные переменные, не будучи независимыми, являются отрицательно связанными. Далее при оценке успешности процесса обхода в ширину используется более точный и детальный алгоритм «анализа в среднем». | ||
Построение пути и процесс обхода в ширину могут в совокупности рассматриваться как алгоритм, который (в случае, если не найдено пропусков) позволяет найти огромный связный компонент. Этот алгоритм весьма эффективен, что иллюстрирует следующая теорема. | |||
'''Теорема 7.''' Огромный компонент <math>G^r_{n,p}</math> может быть построен за время <math>O(n \; log \; n)</math> с вероятностью не менее <math>1 - O(log^2 n)/(n^{\alpha\ /3})</math>, где <math>\alpha\ > 0</math> – константа, которую можно выбрать. | |||
== Применение == | == Применение == | ||
