Случайный регулярный график
Случайный выбранный r -регулярный граф — это граф, из , который обозначает вероятностное пространство всех r -регулярных графов на вершины, где и четный. [1] Таким образом, это особый вид случайного графа , но ограничение регулярности существенно меняет свойства, которые будут соблюдаться, поскольку большинство графов не являются регулярными.
Свойства случайных регулярных графов [ править ]
Как и в случае с более общими случайными графами , можно доказать, что определенные свойства случайных графов –регулярные графы выполняются асимптотически почти наверняка . В частности, для случайный r -регулярный граф большого размера асимптотически почти наверное r -связен . [2] Другими словами, хотя – регулярные графы со связностью менее существуют, вероятность выбора такого графа стремится к 0, так как увеличивается.
Если является положительной константой, и является наименьшим целым числом, удовлетворяющим
тогда асимптотически почти наверняка случайный r -регулярный граф имеет диаметр не более d . Существует также (более сложная) нижняя граница диаметра r -регулярных графов, так что почти все r -регулярные графы (одного и того же размера) имеют почти одинаковый диаметр. [3]
Также известно распределение числа коротких циклов: для фиксированных , позволять быть числом циклов длиной до . Тогда являются асимптотически независимыми случайными величинами Пуассона со средними значениями [4]
Алгоритмы для случайных регулярных графов [ править ]
Эффективно и беспристрастно реализовать случайный выбор r -регулярных графов нетривиально, поскольку большинство графов не являются регулярными. Модель пар (также модель конфигурации ) — это метод, который берет nr точек и разделяет их на n сегментов по r баллов в каждом из них. Случайное сопоставление nr точек и последующее сжатие r точек в каждом блоке в одну вершину дает r -регулярный граф или мультиграф . Если этот объект не имеет кратных ребер или петель (т.е. это граф), то это и есть требуемый результат. В противном случае требуется перезагрузка. [5]
Усовершенствованный метод был разработан Бренданом Маккеем и Николасом Вормальдом. [6]
Ссылки [ править ]
- ^ Бела Боллобас , Случайные графики , 2-е издание, Cambridge University Press (2001), раздел 2.4: Случайные регулярные графики
- ^ Боллобас, раздел 7.6: Случайные регулярные графы
- ^ Боллобас, раздел 10.3: Диаметр случайных регулярных графов
- ^ Боллобас, раздел 2.4: Случайные регулярные графы (следствие 2.19)
- ^ Н. Вормолд, «Модели случайных регулярных графов», в «Обзорах по комбинаторике» , Cambridge University Press (1999), стр. 239–298.
- ^ Б. Маккей и Н. Вормолд, «Равномерное создание случайных регулярных графов средней степени», Журнал алгоритмов , Vol. 11 (1990), стр. 52-67: [1]