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

Новая модель [[случайный граф|случайных графов]], которая была предложена в работе [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.

Рассмотрим несколько важных свойств связности для случайных регулярных графов с ошибочными дугами. Чтобы иметь возможность работать с моделью <math>G^r_{n,p}</math>, в [7] вначале расширяется понятие конфигураций и приводится лемма о переводе между конфигурациями и случайными регулярными графами, введенная Боллобасом [2, 3]; вводится понятие [[случайная конфигурация|случайных конфигураций]], отвечающих за пропущенные дуги, и приводится расширенная лемма о переводе между случайными конфигурациями и случайными регулярными графами с пропущенными дугами.

Согласно [7], для этой новой модели случайных регулярных графов с пропущенными дугами верно следующее:

С технической точки зрения делать какие-либо утверждения о случайных регулярных графах не так просто, как в случае <math>G_{n,p}</math>, в силу стохастических зависимостей от существования дуг, связанных с регулярностью. Введенная Боллобасом [2, 3] нотация [[конфигурация|конфигурации]] предназначена для перевода операторов для случайных регулярных графов в операторы для соответствующих конфигураций, которые не содержат зависимостей между дугами в силу регулярности и с которыми поэтому намного проще работать.

'''Определение 2 (Боллобас, [3])'''. Пусть <math>w = \cup^n_{j=1} w_j</math> – фиксированное множество <math>2m = \sum^n_{j=1} d_j</math> помеченных вершин, где <math>|w_j| = d_j \; </math>. Конфигурация F представляет собой разбиение w на m пар вершин, называемых дугами F.

Пусть дана конфигурация F. Пусть <math>\theta\ (F)</math> – (мульти)граф с множеством вершин V, в котором (i, j) является дугой в том и только том случае, если в F имеется пара (дуга), имеющая один элемент в <math>w_i \; </math>, а другой – в <math>w_j \; </math>. Заметим, что каждый регулярный граф <math>G \in G^r_n</math> имеет форму <math>\theta\ (F)</math> в точности для <math>(r!)^n \; </math> конфигураций. Однако не каждая конфигурация F с <math>d_j = r \; </math> для всех j соответствует ситуации <math>G \in G^r_n</math>, поскольку F может содержать дугу, полностью находящуюся в некотором <math>w_j \; </math>, либо параллельные дуги, связывающие <math>w_i \; </math> и <math>w_j \; </math>.

Для обработки пропущенных дуг в [7] вводится следующее расширение понятия конфигураций:

'''Определение 3 (случайные конфигурации).''' Пусть <math>w = \cup^n_{j=1} w_j</math> – фиксированное множество <math>2m = \sum^n_{j=1} d_j</math> помеченных «вершин», где <math>|w_j| = d_j \; </math>. Пусть F – любая конфигурация множества <math>\varphi\ \;</math> . Взяв каждую дугу из F, удалить ее с вероятностью 1 — p независимым от других образом. Пусть <math>\quad \hat{\phi\ }</math>  – новое множество объектов, а <math>\quad \hat{F}</math> – результат эксперимента. <math>\quad \hat{F}</math> будем называть [[случайная конфигурация|случайной конфигурацией]].

Если ввести для каждой дуги вероятность p, расширение доказательства леммы 1 (поскольку и в <math>\bar{Q}</math>, и в <math>\hat{Q}</math> каждая дуга имеет одну и ту же вероятность быть удаленной одинаково независимо от других, в результате чего модифицированные пространства соответствуют свойствам <math>Q \; </math> и <math>Q^* \;</math>) приводит к следующему расширению случайных конфигураций.

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

Для доказательства используется расширенная для работы с пропущенными дугами техника, предназначенная для недопущения малых разделителей в случайных регулярных графах.

Заметим, что вероятность постоянного возникновения пропущенных дуг существенно изменяет структуру связности регулярного графа в случае низких значений степеней. В частности, использование понятия случайных конфигураций [7] позволяет доказать следующую теорему:

Для доказательства существования компоненты необходимо вначале доказать существование (с высокой вероятностью) достаточно длинного пути (логарифмической длины) в качестве основы для процесса обхода в ширину, начинающегося с вершин того пути, на основе которого создается компонент. В процессе довольно сложного доказательства используются соображения занятости (столбики диаграмм соответствуют вершинам графов, а круги – дугам); однако упоминаемые в ходе него случайные переменные не являются независимыми, и для использования границ Черноффа-Хеффдинга для концентрации необходимо вначале доказать, что эти случайные переменные, не будучи независимыми, являются отрицательно связанными. Далее при оценке успешности процесса обхода в ширину используется более точный и детальный алгоритм «анализа в среднем».

На основе представленных в [7] идей были проведены и другие интересные исследования. Андреас Гердт [4] продолжил работать над темами, представленными в предыдущей ([8]) версии работы [7], и продемонстрировал следующие результаты: если степень r фиксирована, то <math>p = \frac{1}{r - 1}</math> представляет собой пороговую вероятность существования компонента линейного размера в версии почти любого случайного регулярного графа с пропусками дуг. Фактически он демонстрирует, что в случае, если каждая дуга произвольного графа G с максимальной степенью, ограниченной сверху r, имеется в наличии с вероятностью <math>p = \frac{\lambda\ }{r - 1}</math>, где <math>\lambda\ < 1 \; </math>, тогда версия G с пропусками дуг с высокой вероятностью содержит только компоненты, имеющие не более чем логарифмический размер относительно числа вершин. Из этого следует некоторое понятие оптимальности случайных регулярных графов с пропущенными дугами. В [5, 10] исследуются важные свойства расширения случайных регулярных графов с пропущенными дугами; в [9] та же задача рассматривается для случая утолщенных деревьев – распространенного типа топологии сетей. В продолжение этих исследований следовало бы изучить другие комбинаторные свойства случайных регулярных графов с пропущенными дугами, а также предложить для них эффективные алгоритмы.