Связность и отказоустойчивость в случайных регулярных графах: различия между версиями

Перейти к навигации Перейти к поиску
Строка 59: Строка 59:




Рассматривается случай вероятности постоянного возникновения пропущенных дуг f, представляющего наихудший случай для сохранения связности. В [ ] показано, что логарифмических степеней достаточно, чтобы гарантировать, что Grn;p с высокой вероятностью остается сильно связным, несмотря на постоянное возникновение пропусков дуг. Подробнее об этом говорит следующая теорема.
Рассматривается случай вероятности постоянного возникновения пропущенных дуг f, представляющего наихудший случай для сохранения связности. В [7] показано, что логарифмических степеней достаточно, чтобы гарантировать, что <math>G^r_{n,p}</math> с высокой вероятностью остается сильно связным, несмотря на постоянное возникновение пропусков дуг. Подробнее об этом говорит следующая теорема.


Теорема 3. Пусть G – экземпляр Gnr; p, где p = 0(1) и r > a log n, где a > 0 – подходящая константа. 


Тогда G почти наверняка является k-связным, где
'''Теорема 3.''' Пусть G – экземпляр <math>G^r_{n,p}</math>, где <math>p = \Theta(1) \; </math> и <math>r \ge \alpha\ log n</math>, где <math>\alpha > 0 \; </math> – подходящая константа. 
 
Тогда G почти наверняка является k-связным, где <math>k = O\left ( \frac{log \; n}{log \; log \; n} \right )</math>


В доказательстве теоремы используется граница Черноффа для оценки степеней вершин в Grn p и «схожести» Gnr; p и Gn;p0 (свойства которого известны) для подходящим образом выбранного p0.
В доказательстве теоремы используется граница Черноффа для оценки степеней вершин в Grn p и «схожести» Gnr; p и Gn;p0 (свойства которого известны) для подходящим образом выбранного p0.
Источник — http://pco.iis.nsk.su/wega/index.php/Связность_и_отказоустойчивость_в_случайных_регулярных_графах