4551
правка
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 03:12, 24 января 2013
, 24 января 2013→Основные результаты
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
== Основные результаты == | == Основные результаты == | ||
Рассмотрим несколько важных свойств связности для случайных регулярных графов с ошибочными дугами. Чтобы иметь возможность работать с моделью | Рассмотрим несколько важных свойств связности для случайных регулярных графов с ошибочными дугами. Чтобы иметь возможность работать с моделью <math>G^r_{n,p}</math>, в [7] вначале расширяется понятие конфигураций и приводится лемма о переводе между конфигурациями и случайными регулярными графами, введенная Боллобасом [2, 3]; вводится понятие [[случайная конфигурация|случайных конфигураций]], отвечающих за пропущенные дуги, и приводится расширенная лемма о переводе между случайными конфигурациями и случайными регулярными графами с пропущенными дугами. | ||
Согласно [7], для этой новой модели случайных регулярных графов с пропущенными дугами верно следующее: | Согласно [7], для этой новой модели случайных регулярных графов с пропущенными дугами верно следующее: | ||
1. Для всех вероятностей ошибки f = 1 | |||
2. | 1. Для всех вероятностей ошибки <math>f = 1 - p \le n^{- \epsilon\ }</math> (<math>\epsilon\ \ge \frac{3}{2r}</math> фиксировано) и любого <math>r \ge 3</math> наибольшая часть <math>G^r_{n,p}</math> (иными словами, весь граф за вычетом O(1) вершин) остается связной и, таким образом, связная часть графа почти наверняка не может быть выделена, если только не будут удалены более r вершин. Заметим, что ситуация с диапазоном графа и значением r, несмотря на пропуски, очень напоминает свойства <math>G^r_n</math>, являющегося r-связным для <math>r \ge 3</math>. | ||
3. Даже если | |||
2. <math>G^r_{n,p}</math> почти наверняка ''теряет связность'' для константного f и любого r = o(log n), однако почти наверняка ''обладает высокой связностью'' в случае <math>r \ge \alpha\ log n</math>, где <math>\alpha\ > 0</math> – подходящая константа. | |||
3. Даже если <math>G^r_{n,p}</math> теряет связность, он по-прежнему включает огромный компонент меньшего диаметра, даже если r = O(1). | |||
Разработан алгоритм для построения этого огромного компонента за время O(n log n). | Разработан алгоритм для построения этого огромного компонента за время O(n log n). | ||