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

Random regular graph

А случайный р-регулярный график это график выбран из , который обозначает вероятностное пространство всех р-регулярные графики на п вершины, где 3 ≤ р < п и номер даже.[1] Следовательно, это особый вид случайный граф, но ограничение регулярности существенно изменяет свойства, которые будут выполняться, поскольку большинство графов не являются регулярными.

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

Как и в случае с более общими случайные графы, можно доказать, что некоторые свойства случайных р-регулярные графы асимптотически почти наверняка. В частности, для , случайный р-регулярный граф большого размера асимптотически почти наверняка р-связаны.[2] Другими словами, хотя р-регулярные графики со связностью менее р существует, вероятность выбора такого графа стремится к 0 при п увеличивается.

Если > 0 - положительная постоянная, а d наименьшее целое число, удовлетворяющее

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

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

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

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

Уточнение этого метода было разработано Брендан МакКей и Николас Вормальд.[6]

Рекомендации

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