Случайный граф: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Tosha (обсуждение | вклад) |
Нет описания правки |
||
Строка 5:
|заглавие=Random Graphs
|год=2001
|издательство=Cambridge University Press}}</ref>. Теория случайных графов находится на стыке [[Теория графов|теории графов]] и [[Теория вероятностей|теории вероятностей]]. С математической точки зрения случайные графы необходимы для ответа на вопрос о свойствах ''типичных'' графов. Случайные графы нашли практическое применение во всех областях, где нужно смоделировать [[Комплексные сети|сложные сети]] — известно большое число случайных моделей графов, отражающих разнообразные типы сложных сетей в различных областях. В математическом контексте термин ''случайный граф'' означает почти всегда [[Модель Эрдёша — Реньи|модель случайных графов Эрдёша
== Модели случайных графов ==
Строка 14:
|издательство= Academic Press Inc
|место=London}}</ref>.
Различные '''модели случайных графов''' дают различные [[Распределение вероятностей|
Наиболее часто изучаемым является распределение, предложенное {{не переведено 5|Гильберт, Эдгар Нельсон|Гильбертом||Edgar Gilbert}} и обозначаемое <math>G(n,p)</math>, в котором любое возможное ребро появляется независимо с вероятностью <math>0<p<1</math>.
Строка 24:
|издательство=American Mathematical Society}}</ref>.
Близкая к нему [[
Если обозначить <math>N = {n\choose 2},</math> с <math>0\le M \le N</math>, то <math>G(n,p)</math> будет содержать <math>\tbinom NM</math> элементов и любой элемент выпадает с вероятностью <math>\tbinom NM^{-1}</math><ref name = "Random Graphs2" />.
Эту модель можно рассматривать как снимок для некоторого момента времени (''M'') '''[[Случайный процесс|случайного процесса]] на графе''' <math>\tilde{G}_n</math>, который начинается с ''n'' вершин без рёбер и на каждом шагу добавляется новое ребро, выбираемое равномерно из множества отсутствующих рёбер.
Строка 34:
Оказывается, что если множество вершин [[Счётное множество|счётно]], то существует, {{не переведено 5|С точностью до|с точностью до||up to}} [[Изоморфизм графов|изоморфизма]], единственный граф с такими свойствами, а именно [[граф Радо]]. Таким образом, любой счётный бесконечный граф почти достоверно является графом Радо, который по этой причине иногда называют просто '''случайным графом'''. Однако аналогичный результат неверен для несчётных графов, для которых существует множество (неизоморфных) графов, удовлетворяющих вышеупомянутому условию.
Другая модель, обобщающая модель Гильберта случайного графа, — это '''модель случайного скалярного произведения'''. Граф случайного скалярного произведения связывает с каждой вершиной [[Векторное пространство|вещественный вектор]]. Вероятность ребра ''uv'' между любыми вершинами ''u'' и ''v'' является некоторой функцией [[Скалярное произведение|
{{не переведено 5|Матрица вероятности сети|Матрицы вероятности сети||network probability matrix}} моделируют случайные графы через вероятности рёбер <math>p_{i,j}</math> таким образом, что данное ребро <math>e_{i,j}</math> существует в указанный период времени. Эту модель можно распространить на ориентированные и неориентированные графы, взвешенные и не взвешенные, на статические и динамические.
Строка 88:
== Случайные деревья ==
{{не переведено 5|Случайное дерево|Случайным деревом||random tree}} называется [[Дерево (теория графов)|дерево]] или {{не переведено 5|Ориентированное дерево|ориентированное дерево||Arborescence (graph theory)}}, образованное [[Случайный процесс|
== История ==
Строка 119:
== Литература ==
* {{книга | автор = [[Райгородский, Андрей Михайлович|А.М. Райгородский]] | заглавие = Модели случайных графов | место
{{вс}}
{{rq|checktranslate}}
[[Категория:Теория графов]]
[[Категория:Теория вероятностей]]
| |||