Введение

Граф, сгенерированный случайным процессом, счетный бесконечный случайный граф.

В математике случайный граф – это общий термин для обозначения распределений вероятностей над графами. Случайные графы могут быть описаны просто распределением вероятностей или случайным процессом, который их порождает. Теория случайных графов находится на пересечении теории графов и теории вероятностей. С математической точки зрения, случайные графы используются для ответа на вопросы о свойствах типичных графов. Их практическое применение можно найти во всех областях, где необходимо моделировать сложные сети – существует множество моделей случайных графов, отражающих разнообразие типов сложных сетей, встречающихся в различных областях. В математическом контексте случайный граф почти исключительно относится к модели случайного графа Эрдоша — Реньи. В других контекстах любую модель графа можно назвать случайным графом.

Модели

Случайный граф получают, начиная с множества из n изолированных вершин и последовательно добавляя ребра между ними случайным образом. Целью исследования в этой области является определение того, на каком этапе с наибольшей вероятностью возникнет определенное свойство графа. Различные модели случайных графов порождают различные распределения вероятностей на графах. Наиболее часто изучаемой является модель, предложенная Эдгаром Гилбертом, обозначаемая G(n,p), в которой каждое возможное ребро возникает независимо с вероятностью 0 < p < 1. Вероятность получения конкретного случайного графа с m ребрами равна, а близко связанной моделью является модель Эрдоша — Рени, обозначаемая G(n,M), которая присваивает равную вероятность всем графам, имеющим ровно M ребер. При 0 ≤ M ≤ N, G(n,M) имеет элементов, и каждый элемент встречается с вероятностью. Случайные регулярные графы представляют собой особый случай, свойства которого могут отличаться от свойств случайных графов в общем случае. Как только у нас есть модель случайных графов, любая функция на графах становится случайной величиной. Изучение этой модели направлено на определение того, может ли возникнуть свойство, или, по крайней мере, на оценку вероятности его возникновения.

Цветение

Для случайного графа G порядка n с множеством вершин V(G) = {1, ..., n}, при использовании жадного алгоритма по числу цветов, вершины можно раскрасить цветами 1, 2, ... (вершина 1 раскрашивается в цвет 1, вершина 2 раскрашивается в цвет 1, если она не смежна с вершиной 1, иначе – в цвет 2, и так далее).

Случайные деревья

Случайное дерево — это дерево или арбоrescence, формируемое стохастическим процессом. В широком диапазоне случайных графов порядка n и размера M(n) распределение числа древесных компонент порядка k асимптотически следует распределению Пуассона. К типам случайных деревьев относятся равномерное остовное дерево, случайное минимальное остовное дерево, случайное двоичное дерево, треп, дерево быстрого поиска в пространстве, броуновское дерево и случайный лес.

Условные случайные графики

Рассмотрим данную модель случайного графа, определенную на пространстве вероятностей, и пусть f — вещественнозначная функция, которая каждому графу из G присваивает вектор из m свойств. Для фиксированного набора свойств, условные случайные графы представляют собой модели, в которых вероятностная мера присваивает нулевую вероятность всем графам, не удовлетворяющим условию '. Частными случаями являются условно-однородные случайные графы, где всем графам с заданными свойствами присваивается одинаковая вероятность. Их можно рассматривать как обобщение модели Эрдоша — Реньи G(n,M), когда информация для обуславливания не обязательно является числом ребер M, а может быть любым другим произвольным свойством графа. В этом случае доступно очень мало аналитических результатов, и для получения эмпирических распределений средних свойств требуется моделирование.

История

Самое раннее использование модели случайного графа было осуществлено Хелен Холл Дженнингс и Джейкобом Морено в 1938 году, где "случайная социограмма" (направленная модель Эрдоша — Рени) рассматривалась при исследовании, сравнивающем долю взаимных связей в их сетевых данных со случайной моделью. Другое использование под названием "случайная сеть" было предложено Рэем Соломоноффом и Анатолем Рапопортом в 1951 году, с использованием модели направленных графов с фиксированной исходящей степенью и случайным выбором связей с другими вершинами. Модель случайных графов Эрдоша — Рени была впервые определена Полом Эрдошем и Альфредом Рени в их статье 1959 года "О случайных графах" и независимо от них — Гилбертом в его статье "Случайные графы".