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

Новая модель случайных графов, которая была предложена в работе [7], касается случайных графов с пропущенными дугами (далее обозначаемыми Grn p), полученных путем выбора дуг из случайного элемента множества всех регулярных графов степени r независимым образом, с вероятностью p. Такие графы могут представлять сеть коммуникаций, в которой связи обрываются независимо друг от друга с вероятностью f = 1 — p. Формальное определение пространства вероятностей Grn p:

Определение 1 (пространство вероятности Grn). Пусть Gnr – пространство вероятности всех случайных регулярных графов с n вершинами, каждая вершина которых имеет степень r. Пространство вероятности Grn p случайных регулярных графов с ошибочными дугами строится на основании двух последовательных случайных экспериментов: вначале из пространства Grn выбирается случайный регулярный граф, а затем каждая дуга случайным и независимым образом удалется из этого графа с вероятностью f = 1 — p.

»Важное свойство связности Gnr; p исследуется путем оценки диапазонов r;f, для которых, с высокой вероятностью, графы Gnr; p (а) являются сильно связными; (б) становятся несвязными и (в) содержат большой (размера 0{n)) связный компонент меньшего диаметра.