Лекция
Привет, Вы узнаете о том , что такое случайный граф, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое случайный граф , настоятельно рекомендую прочитать все из категории Теория вероятностей. Математическая статистика и Стохастический анализ .
В математике случайный граф — это общий термин для обозначения вероятностного распределения графов. Случайные графы можно описать просто распределением вероятности или случайным процессом, создающим эти графы . Теория случайных графов находится на стыке теории графов и теории вероятностей. С математической точки зрения случайные графы необходимы для ответа на вопрос о свойствах типичных графов. Случайные графы нашли практическое применение во всех областях, где нужно смоделировать сложные сети — известно большое число случайных моделей графов, отражающих разнообразные типы сложных сетей в различных областях. В математическом контексте термин случайный граф означает почти всегда модель случайных графов Эрдеш — Реньи . В других контекстах любая модель графов означает случайный граф.
Случайный граф получается из множества n изолированных вершин путем последовательного случайного добавления соединяющих вершины ребер. Целью моделирования случайных графов является определение того, на каком этапе появляется определенное свойство графа . Различные модели случайных графов дают различные распределения вероятностей на графе. Наиболее часто изучаемым является распределение, предложенное Гильбертом и обозначаемое G(n,p), в котором любое возможное ребро появляется независимо с вероятностью 0 < p < 1. Вероятность случайного графа с m ребрами равна pm(1−p)N−m . Близкая к нему модель Эрдеша — Реньи[en], обозначаемая G(n,M), дает одинаковую вероятность всем графам, имеющим в точности M ребер. Если обозначить 
с 0 ≤ M ≤ N, G(n,p) будет содержать {\displaystyle 
элементов и любой элемент выпадает с вероятностью 
. Эту модель можно рассматривать как снимок для некоторого момента времени (M) случайного процесса на графе 
, который начинается с n вершин без ребер и на каждом шагу добавляется новое ребро, выбираемое равномерно из множества отсутствующих ребер.
Если же начинать с бесконечного множества вершин и выбирать каждое возможное ребро независимо с вероятностью 0 < p < 1, получится объект G, называемый бесконечным случайным графом. Об этом говорит сайт https://intellect.icu . За исключением тривиальных случаев, когда p равно 0 или 1, такой G почти достоверно обладает следующими свойствами:
Если заданы любые n + m элементов
, существует вершина c в V, которая смежна с каждой вершиной
и не связна ни с одной из
.
Оказывается, что если множество вершин счетно, то существует, с точностью до[en] изоморфизма, единственный граф с такими свойствами, а именно граф Радо. Таким образом, любой счетный бесконечный граф почти достоверно является графом Радо, который по этой причине иногда называют просто случайным графом. Однако аналогичный результат неверен для несчетных графов, для которых существует множество (неизоморфных) графов, удовлетворяющих вышеупомянутому условию.
Другая модель, обобщающая модель Гильберта случайного графа, — это модель случайного скалярного произведения. Граф случайного скалярного произведения связывает с каждой вершиной вещественный вектор . Вероятность ребра uv между любыми вершинами u и v является некоторой функцией скалярного произведения u • v соответствующих им векторов.
Матрицы вероятности сети моделируют случайные графы через вероятности ребер 
таким образом, что данное ребро 
существует в указанный период времени. Эту модель можно распространить на ориентированные и неориентированные графы, взвешенные и не взвешенные, на статические и динамические.
Для M ≃ pN, где N — максимально возможное число ребер, чаще всего используются модели G(n,M) и G(n,p), почти всегда взаимозаменяемые
Случайный регулярный граф образует специальный случай, имеющий свойства, которые в общем случае могут отличаться от случайных графов.
Если мы имеем модель случайных графов, любая функция на графах становится случайной величиной. Задача изучения этой модели — определить, или, по крайней мере, оценить вероятность появления свойства .
Термин «почти достоверно» в контексте случайных графов относится к последовательности пространств и вероятностей, таких что вероятность ошибки стремится к нулю .
Теория случайных графов изучает типичные свойства случайных графов, которые выполняются с большой степенью вероятности для графов, полученных для определенного распределения. Например, мы можем спросить для заданных значений n и p, какова вероятность , что G(n,p) связен. При изучении таких вопросов исследователи часто концентрируются на асимптотическом поведении случайных графов — значениях, к которым стремятся различные вероятности при росте n. Теория перколяции описывает связность случайных графов, в особенности неограниченно больших.
Перколяция связана с устойчивостью графа (называемого также сетью). Пусть дан случайный граф с n вершинами и средней степенью 
. Удалим случайную 1−p часть ребер и оставим p часть. Существует критический порог перкуляции 
, ниже которой сеть становится фрагментированной, в то время как выше pcсуществуют огромные компоненты связности .
Случайные графы широко используются в вероятностном методе, когда пытаются доказать существование графов с определенными свойствами. Существование свойства на случайных графах могут часто иметь следствием, по лемме регулярности Семереди , существование этого свойства почти для всех графов.
Для случайных регулярных графов[en] G(n,r-reg) — это множество r-регулярных графов с r = r(n), таких что n и m — натуральные числа , 3 ≤ r < n, и rn = 2m четно .
Последовательность степеней графа G в Gn зависит только от числа ребер в множествах
Если множество ребер M в случайном графе GM достаточно большое, чтобы почти все GM имели минимальную степень не меньше 1, то почти любой GM связен и, для четного n, почти любой GM содержит совершенное паросочетание. В частности, в момент, когда исчезает последняя изолированная вершина, почти во всех случайных графах, граф становится связным
Почти любой процесс построения графа с четным числом вершин при достижении минимальной степени 1 или случайного графа при достижении чуть больше, чем (n/4)log(n) ребер с вероятностью, близкой к 1 обеспечивает существование полного паросочетания, за исключением, может быть, одной вершины.
Для некоторой константы c почти каждый помеченный граф с n вершинами и как минимум cnlog(n) ребрами является гамильтоновым. С вероятностью, стремящейся к 1, добавление ребра, увеличивающее минимальную степень графа до 2, делает его гамильтоновым.
Если задан случайный граф G порядка n с вершинами V(G) = {1, …, n}, раскраску можно получить с помощью жадного алгоритма (вершина 1 выкрашивается цветом 1, вершина 2 получает цвет 1 если она не смежна 1, в противном получает цвет 2, и так далее) .
Случайным деревом называется дерево или ориентированное дерево , образованное случайным процессом. В большом диапазоне случайных графов порядка n и размера M(n) распределение числа деревьев порядка k асимптотически подчинено закону Пуассона . Типы случайных деревьев включают униформные стягивающие деревья[en], случайные минимальные стягивающие деревья , случайные бинарные деревья [en], декартовы деревья, быстро просматриваемые случайные деревья[en], броуновские деревья и случайные леса.
Случайные графы впервые определены Эрдешем и Реньи в книге 1959 года «On Random Graphs» и независимо Гильбертом в его статье «Random graphs» .
Представленные результаты и исследования подтверждают, что применение искусственного интеллекта в области случайный граф имеет потенциал для революции в различных связанных с данной темой сферах. Надеюсь, что теперь ты понял что такое случайный граф и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория вероятностей. Математическая статистика и Стохастический анализ
Из статьи мы узнали кратко, но содержательно про случайный граф
Комментарии
Оставить комментарий
Теория вероятностей. Математическая статистика и Стохастический анализ
Термины: Теория вероятностей. Математическая статистика и Стохастический анализ