4551
правка
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 02:57, 24 января 2013
, 24 января 2013→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
== Постановка задачи == | == Постановка задачи == | ||
Новая модель случайных графов, которая была предложена в работе [7], касается случайных графов с пропущенными дугами (далее обозначаемыми <math>G^r_{n,p}</math>), полученных путем выбора дуг из случайного элемента множества всех регулярных графов степени r независимым образом, с вероятностью p. Такие графы могут представлять сеть коммуникаций, в которой связи обрываются независимо друг от друга с вероятностью f = 1 — p. Формальное определение пространства вероятностей <math>G^r_{n,p}</math> выглядит следующим образом: | Новая модель [[случайный граф|случайных графов]], которая была предложена в работе [7], касается случайных графов с пропущенными дугами (далее обозначаемыми <math>G^r_{n,p}</math>), полученных путем выбора дуг из случайного элемента множества всех регулярных графов степени r независимым образом, с вероятностью p. Такие графы могут представлять сеть коммуникаций, в которой связи обрываются независимо друг от друга с вероятностью f = 1 — p. Формальное определение пространства вероятностей <math>G^r_{n,p}</math> выглядит следующим образом: | ||
'''Определение 1 (пространство вероятности <math>G^r_{n,p}</math>).''' Пусть <math>G^r_n</math> – пространство вероятности всех случайных регулярных графов с n вершинами, каждая вершина которых имеет степень r. Пространство вероятности <math>G^r_{n,p}</math> случайных регулярных графов с пропущенными дугами строится на основании двух последовательных случайных экспериментов: вначале из пространства <math>G^r_n</math> выбирается случайный регулярный граф, а затем каждая дуга случайным и независимым образом удаляется из этого графа с вероятностью f = 1 — p. | '''Определение 1 (пространство вероятности <math>G^r_{n,p}</math>).''' Пусть <math>G^r_n</math> – пространство вероятности всех случайных регулярных графов с n вершинами, каждая вершина которых имеет степень r. Пространство вероятности <math>G^r_{n,p}</math> случайных регулярных графов с пропущенными дугами строится на основании двух последовательных случайных экспериментов: вначале из пространства <math>G^r_n</math> выбирается случайный регулярный граф, а затем каждая дуга случайным и независимым образом удаляется из этого графа с вероятностью f = 1 — p. | ||