Случайный регулярный график
- Случайный r-регулярный граф выбирается из G n,r , вероятностного пространства всех r-регулярных графов на n вершинах.
- Ограничение регулярности значительно изменяет свойства случайных графов, так как большинство графов не являются регулярными.
- Для r ≥ 3, случайный r-регулярный граф большого размера почти наверняка является r-связным.
- Асимптотически почти наверняка случайный r-регулярный граф имеет диаметр не более d, если выполняется определенное условие.
- Распределение количества коротких циклов известно для фиксированных m ≥ 3, и Y i являются асимптотически независимыми пуассоновскими случайными величинами.
- Реализация случайного выбора r-регулярных графов требует нетривиальных методов, так как большинство графов не являются регулярными.
- Модель сопряжения (модель конфигурации) — это метод, который разбивает nr точек на n сегментов с r точками в каждом из них, и затем объединяет r точек в каждом сегменте в одну вершину.
Полный текст статьи: