Случайный регулярный граф

Случайный r -регулярный граф - это граф , выбранный из , что обозначает вероятностное пространство всех r -регулярных графов на вершинах, где и четно. ^[1] Таким образом, это особый вид случайного графа , но ограничение регулярности существенно изменяет свойства, которые будут сохраняться, поскольку большинство графов не являются регулярными. ${\displaystyle {\mathcal {G}}_{n,r}}$ ${\displaystyle n}$ ${\displaystyle 3\leq r<n}$ ${\displaystyle nr}$

Свойства случайных регулярных графов

Как и в случае более общих случайных графов , можно доказать, что некоторые свойства случайных -регулярных графов выполняются асимптотически почти наверняка . В частности, для случайный r -регулярный граф большого размера асимптотически почти наверняка r -связен . ^[2] Другими словами, хотя существуют -регулярные графы со связностью, меньшей, чем , вероятность выбора такого графа стремится к 0 по мере увеличения. ${\displaystyle m}$ ${\displaystyle r\geq 3}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle n}$

Если — положительная константа, а — наименьшее целое число, удовлетворяющее ${\displaystyle \epsilon >0}$ ${\displaystyle d}$

${\displaystyle (r-1)^{d-1}\geq (2+\epsilon )rn\ln n}$

тогда, асимптотически почти наверняка, случайный r -регулярный граф имеет диаметр не более d . Существует также (более сложная) нижняя граница диаметра r -регулярных графов, так что почти все r -регулярные графы (одного и того же размера) имеют почти одинаковый диаметр. ^[3]

Известно также распределение числа коротких циклов: при фиксированном пусть — число циклов длиной до . Тогда — асимптотически независимые пуассоновские случайные величины со средними ^[4] ${\displaystyle m\geq 3}$ ${\displaystyle Y_{3},Y_{4},...Y_{m}}$ ${\displaystyle m}$ ${\displaystyle Y_{i}}$

${\displaystyle \lambda _{i}={\frac {(r-1)^{i}}{2i}}}$

Алгоритмы для случайных регулярных графов

Нетривиально реализовать случайный выбор r -регулярных графов эффективно и беспристрастно, поскольку большинство графов не являются регулярными. Модель спаривания (также модель конфигурации ) — это метод, который берет nr точек и разбивает их на n сегментов с r точками в каждом из них. Взяв случайное соответствие nr точек, а затем сжав r точек в каждом сегменте в одну вершину, получаем r -регулярный граф или мультиграф . Если этот объект не имеет кратных ребер или петель (т. е. это граф), то это требуемый результат. Если нет, требуется перезапуск. ^[5]

Усовершенствование этого метода было разработано Бренданом Маккеем и Николасом Вормолдом. ^[6]

Ссылки

1. Бела Боллобаш , Случайные графы , 2-е издание, Cambridge University Press (2001), раздел 2.4: Случайные регулярные графы
2. Боллобас, раздел 7.6: Случайные регулярные графы
3. Боллобас, раздел 10.3: Диаметр случайных регулярных графов
4. Боллобас, раздел 2.4: Случайные регулярные графы (следствие 2.19)
5. Н. Вормальд, «Модели случайных регулярных графов», в Обзорах комбинаторики , Cambridge University Press (1999), стр. 239-298.
6. Б. Маккей и Н. Вормалд, «Равномерная генерация случайных регулярных графов умеренной степени», Журнал алгоритмов , т. 11 (1990), стр. 52-67: [1]