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

редактировать

A случайный r-регулярный граф - это граф, выбранный из $G n, r {\ displaystyle {\ mathcal {G}} _ {n, r}}$ ${\ displaystyle {\ mathcal {G}} _ {n, r}}$ , который обозначает вероятностное пространство всех r-регулярных графов на n вершинах, где 3 ≤ r < n and nr is even. It is therefore a particular kind of случайный граф, но ограничение регулярности существенно изменяет свойства, которые будут сохраняться, поскольку большинство графов не являются регулярными.

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

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

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

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

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

Распределение числа коротких циклов также известно: при фиксированном m ≥ 3 пусть Y 3,Y4,…, Y m - количество циклов длиной до m. Тогда Y i являются асимптотически независимыми случайными величинами Пуассона со средними значениями

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

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

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

Усовершенствованный метод был разработан Бренданом МакКеем и Николасом Вормолдом.

Ссылки