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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Модели случайных графов[править | править вики-текст]

Случайный граф получается из множества n изолированных вершин путём последовательного случайного добавления соединяющих вершины рёбер. Целью моделирования случайных графов является определение того, на каком этапе появляется определённое свойство графа[2]. Различные модели случайных графов дают различные распределения вероятностей на графе. Наиболее часто изучаемым является распределение, предложенное Гильбертом[en] и обозначаемое G(n,p), в котором любое возможное ребро появляется независимо с вероятностью 0 < p < 1. Вероятность случайного графа с m рёбрами равна pm(1−p)Nm[3]. Близкая к нему модель Эрдёша–Реньи[en], обозначаемая G(n,M), даёт одинаковую вероятность всем графам, имеющим в точности M рёбер. Если обозначить N = \begin{bmatrix} n\\2 \end{bmatrix}, с 0 ≤ MN, G(n,p) будет содержать \begin{bmatrix} N\\M \end{bmatrix} элементов и любой элемент выпадает с вероятностью \begin{bmatrix} N \\ M \\ \end{bmatrix}^{-1}.[2] Эту модель можно рассматривать как снимок для некоторого момента времени (M) случайного процесса на графе \tilde{G}_n, который начинается с n вершин без рёбер и на каждом шагу добавляется новое ребро, выбираемое равномерно из множества отсутствующих рёбер.

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

Если заданы любые n + m элементов a_1,\ldots, a_n,b_1,\ldots, b_m \in V, существует вершина c в V, которая смежна с каждой вершиной a_1,\ldots, a_n и не связна ни с одной из b_1,\ldots, b_m.

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

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

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

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

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

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

Терминология[править | править вики-текст]

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

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

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

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

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

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

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

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

Если множество рёбер M в случайном графе GM достаточно большое, чтобы почти все GM имели минимальную степень не меньше 1, то почти любой GM связен и, для чётного n, почти любой GM содержит совершенное паросочетание. В частности, в момент, когда исчезает последняя изолированная вершина почти во всех случайных графах, граф становится связным.[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]

Случайные деревья[править | править вики-текст]

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

История[править | править вики-текст]

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

  1. 1 2 Béla Bollobás[en] Random Graphs. — Cambridge University Press, 2001.
  2. 1 2 3 4 5 6 Béla Bollobás[en] Random Graphs. — London: Academic Press Inc., 1985.
  3. 1 2 3 Béla Bollobás[en] Probabilistic Combinatorics and Its Applications. — Providence: American Mathematical Society, 1991.
  4. 1 2 ">Handbook of Graphs and Networks. — Weinheim: Wiley VCH, 2003.
  5. 1 2 E. N. Gilbert Random graphs. — Annals of Mathematical Statistics. — 1959. — Т. 30. — С. 1141–1144. — DOI:10.1214/aoms/1177706098.
  6. M. E. J. Newman Networks: An Introduction. — Oxford, 2010.
  7. Reuven Cohen, Шломо Хавлин[en] Complex Networks: Structure, Robustness and Function. — Cambridge University Press, 2010.
  8. 1 2 P. Erdős, A Rényi On Random Graphs I. — Publ. Math.. — 1959. — Т. 6. — С. 290-297.