Случайный граф

Случайный граф получается из множества n изолированных вершин путём последовательного случайного добавления соединяющих вершины рёбер. Целью моделирования случайных графов является определение того, на каком этапе появляется определённое свойство графа[2]. Различные модели случайных графов дают различные распределения вероятностей на графе.

Наиболее часто изучаемым является распределение, предложенное Гильбертом и обозначаемое ${\displaystyle G(n,p)}$, в котором любое возможное ребро появляется независимо с вероятностью ${\displaystyle 0<p<1}$. Вероятность получения графа с m рёбрами равна ${\displaystyle {\tbinom {N}{m}}}$ ${\displaystyle p^{m}(1-p)^{N-m}}$ где ${\displaystyle N={\tbinom {n}{2}}}$[3].

Близкая к нему модель Эрдёша — Реньи, обозначаемая ${\displaystyle G(n,M)}$, даёт одинаковую вероятность всем графам, имеющим в точности M рёбер. Если обозначить ${\displaystyle N={n \choose 2},}$ с ${\displaystyle 0\leq M\leq N}$, то ${\displaystyle G(n,p)}$ будет содержать ${\displaystyle {\tbinom {N}{M}}}$ элементов и любой элемент выпадает с вероятностью ${\displaystyle {\tbinom {N}{M}}^{-1}}$[2]. Эту модель можно рассматривать как снимок для некоторого момента времени (M) случайного процесса на графе ${\displaystyle {\tilde {G}}_{n}}$, который начинается с n вершин без рёбер и на каждом шагу добавляется новое ребро, выбираемое равномерно из множества отсутствующих рёбер.

Если же начинать с бесконечного множества вершин и выбирать каждое возможное ребро независимо с вероятностью 0 < p < 1, получится объект G, называемый бесконечным случайным графом. За исключением тривиальных случаев, когда p равно 0 или 1, такой G почти достоверно обладает следующими свойствами:

Если заданы любые n + m элементов ${\displaystyle a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V}$, существует вершина c в V, которая смежна с каждой вершиной ${\displaystyle a_{1},\ldots ,a_{n}}$ и не связна ни с одной из ${\displaystyle b_{1},\ldots ,b_{m}}$.

Оказывается, что если множество вершин счётно, то существует, с точностью до изоморфизма, единственный граф с такими свойствами, а именно граф Радо. Таким образом, любой счётный бесконечный граф почти достоверно является графом Радо, который по этой причине иногда называют просто случайным графом. Однако аналогичный результат неверен для несчётных графов, для которых существует множество (неизоморфных) графов, удовлетворяющих вышеупомянутому условию.

Другая модель, обобщающая модель Гильберта случайного графа, — это модель случайного скалярного произведения. Граф случайного скалярного произведения связывает с каждой вершиной вещественный вектор. Вероятность ребра uv между любыми вершинами u и v является некоторой функцией скалярного произведения u • v соответствующих им векторов.

Матрицы вероятности сети моделируют случайные графы через вероятности рёбер ${\displaystyle p_{i,j}}$ таким образом, что данное ребро ${\displaystyle e_{i,j}}$ существует в указанный период времени. Эту модель можно распространить на ориентированные и неориентированные графы, взвешенные и не взвешенные, на статические и динамические.

Для M ≃ pN, где N — максимально возможное число рёбер, чаще всего используются модели G(n,M) и G(n,p), почти всегда взаимозаменяемые[4].

Случайный регулярный граф образует специальный случай, имеющий свойства, которые в общем случае могут отличаться от случайных графов.

Если мы имеем модель случайных графов, любая функция на графах становится случайной величиной. Задача изучения этой модели — определить, или, по крайней мере, оценить вероятность появления свойства[3].

Термин «почти достоверно» в контексте случайных графов относится к последовательности пространств и вероятностей, таких что вероятность ошибки стремится к нулю[3].

Теория случайных графов изучает типичные свойства случайных графов, которые выполняются с большой степенью вероятности для графов, полученных для определённого распределения. Например, мы можем спросить для заданных значений n и p, какова вероятность, что G(n,p) связен. При изучении таких вопросов исследователи часто концентрируются на асимптотическом поведении случайных графов — значениях, к которым стремятся различные вероятности при росте n. Теория перколяции описывает связность случайных графов, в особенности неограниченно больших.

Перколяция связана с устойчивостью графа (называемого также сетью). Пусть дан случайный граф с n вершинами и средней степенью ${\displaystyle \langle k\rangle }$. Удалим случайную ${\displaystyle 1-p}$ часть рёбер и оставим ${\displaystyle p}$ часть. Существует критический порог перколяции ${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$, ниже которой сеть становится фрагментированной, в то время как выше ${\displaystyle p_{c}}$ существуют огромные компоненты связности[1][5][4][6] [7][8].

Случайные графы широко используются в вероятностном методе, когда пытаются доказать существование графов с определёнными свойствами. Существование свойства на случайных графах могут часто иметь следствием, по лемме регулярности Семереди, существование этого свойства почти для всех графов.

Для случайных регулярных графов G(n,r-reg) — это множество r-регулярных графов с r = r(n), таких что n и m — натуральные числа, 3 ≤ r < n, и rn = 2m чётно[2].

Последовательность степеней графа G в Gⁿ зависит только от числа рёбер в множествах[2]

${\displaystyle V_{n}^{(2)}=\left\{ij\$ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.}

Если множество рёбер M в случайном графе G_M достаточно большое, чтобы почти все G_M имели минимальную степень не меньше 1, то почти любой G_M связен и, для чётного n, почти любой G_M содержит совершенное паросочетание. В частности, в момент, когда исчезает последняя изолированная вершина, почти во всех случайных графах, граф становится связным[2].

Почти любой процесс построения графа с чётным числом вершин при достижении минимальной степени 1 или случайного графа при достижении чуть больше, чем (n/4)log(n) рёбер с вероятностью, близкой к 1 обеспечивает существование полного паросочетания, за исключением, может быть, одной вершины.

Для некоторой константы c почти каждый помеченный граф с n вершинами и как минимум cnlog(n) рёбрами является гамильтоновым. С вероятностью, стремящейся к 1, добавление ребра, увеличивающее минимальную степень графа до 2, делает его гамильтоновым.

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

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

Случайные графы впервые определены Эрдёшем и Реньи в книге 1959 года «On Random Graphs»[8] и независимо Гильбертом в его статье «Random graphs»[5].

• Граф Радо
• Сложные сети
• Перколяция

• А.М. Райгородский. Модели случайных графов. — М.: МЦНМО, 2011. — 136 с. — ISBN 978-5-94057-840-6.