Jump to content

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

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

Свойства случайных регулярных графов [ править ]

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

Если является положительной константой, и является наименьшим целым числом, удовлетворяющим

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

Также известно распределение числа коротких циклов: для фиксированных , позволять быть числом циклов длиной до . Тогда являются асимптотически независимыми случайными величинами Пуассона со средними значениями [4]

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

Эффективно и беспристрастно реализовать случайный выбор 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. ^ Б. Маккей и Н. Вормолд, «Равномерное создание случайных регулярных графов средней степени», Журнал алгоритмов , Vol. 11 (1990), стр. 52-67: [1]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f49927479919f33586df3759300df252__1631261760
URL1:https://arc.ask3.ru/arc/aa/f4/52/f49927479919f33586df3759300df252.html
Заголовок, (Title) документа по адресу, URL1:
Random regular graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)