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