Редактирование: Участник:Quarter

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
{{Определение
 
{{Определение
 
|id=def_degree_dist
 
|id=def_degree_dist
|definition='''Распределение степеней вершин случайного графа''' - это функция <tex>P(x)</tex>, определённая на <tex>\mathbb{R}</tex> как <tex>P(\xi=x)</tex>, то есть выражающая вероятность того, что вершина <tex>\xi</tex> имеет степень <tex>x</tex>. Другими словами, распределение степеней <tex>P(k)</tex> графа определяется как доля узлов, имеющих степень <tex>k</tex>.
+
|definition='''Распределение степеней вершин случайного графа''' - это функция <tex>P(x)</tex>, определённая на <tex>\mathbb{R}</tex> как <tex>P(\xi=x)</tex>, то есть выражающая вероятность того, что вершина <tex>\xi</tex> в графе <tex>G(n, p)</tex> имеет степень <tex>x</tex>
 
}}
 
}}
 +
 +
Другими словами, распределение степеней <tex>P(k)</tex> графа определяется как доля узлов, имеющих степень <tex>k</tex>.
 +
 
{{Пример
 
{{Пример
 
|id=example_1
 
|id=example_1
|example=Если есть в общей сложности <tex>n</tex> узлов в графе и из них <tex>n_k</tex> имеют степень <tex>k</tex>, то <tex>P(k) = \frac{n_k}{n}</tex>. Другими словами, <tex>P(k)</tex> равно вероятности того, что отдельно взятая вершина имеет степень <tex>k</tex>.
+
|example=Если есть в общей сложности <tex>n</tex> узлов в графе и из них <tex>n_k</tex> имеют степень <tex>k</tex>, то <tex>P(k) = \frac{n_k}{n}</tex>. Другими словами, <tex>P(k)</tex> равно вероятности того, что отдельно взятая вершина в <tex>G(n, p)</tex> имеет степень <tex>k</tex>.
 
}}
 
}}
  
{{Утверждение
+
== Биноминальное распределение ==
|statement=Дан случайный граф <tex>G(n, p)</tex> в биноминальной модели. Тогда для него распределение степеней вершин
+
Случайный граф <tex>G(n, p)</tex> имеет биномиальное распределение степеней вершин <tex>k</tex>:
 
<p>
 
<p>
 
<tex>
 
<tex>
Строка 18: Строка 21:
 
</tex>
 
</tex>
 
</p>
 
</p>
|proof=Действительно, если вероятность появления ребра <tex>p</tex>, то вероятность появления ровно <tex>k</tex> рёбер у вершины равна <tex>p^k(1-p)^{n-1-k}</tex>([[схема Бернулли]]). Таких наборов рёбер у одной вершины всего <tex>{n-1 \choose k}</tex>, откуда получаем искомое распределение.
+
Действительно, если вероятность появления ребра <tex>p</tex>, то вероятность появления ровно <tex>k</tex> рёбер у вершины равна <tex>p^k(1-p)^{n-1-k}</tex>(схема Бернулли). Таких наборов рёбер у одной вершины всего <tex>{n-1 \choose k}</tex>, откуда получаем искомое распределение.
}}
+
 
 +
== Равномерное распределение ==
 +
Модель равномерного распределения подразумевает предположение о том, что все графы с <tex>m</tex> рёбрами равновероятны. Здесь имеем <tex>G(n, m)</tex> - граф на <tex>n</tex> вершинах с <tex>m</tex> рёбрами. Задача стоит уже по-другому - распределить <tex>m</tex> рёбер по <tex>{n \choose 2}</tex> местам с точностью до изоморфизма.
 +
 
 +
Её можно переформулировать следующим образом: найдём число разбиений мультимножества из <tex>m</tex> одинаковых чисел на <tex>n</tex> множеств, возможно пустых(или на не более <tex>n</tex> непустых). Эта задача сводится к [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B0%D1%85%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D1%80%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B9_%D1%87%D0%B8%D1%81%D0%BB%D0%B0_%D0%BD%D0%B0_%D1%81%D0%BB%D0%B0%D0%B3%D0%B0%D0%B5%D0%BC%D1%8B%D0%B5 задаче о нахождении количества разбиений на слагаемые].
 +
 
  
 
== Распределение максимальной степени вершин ==
 
== Распределение максимальной степени вершин ==
 
{{Определение
 
{{Определение
 
|id=def_max_degree_dist
 
|id=def_max_degree_dist
|definition='''Распределение максимальной степени вершин случайного графа''' - это функция <tex>Q(x)</tex>, определённая на <tex>\mathbb{R}</tex> как <tex>P(\xi=x)</tex>, то есть выражающая вероятность того, что максимальная степень вершины <tex>\xi</tex> равна <tex>x</tex>.
+
|definition='''Распределение максимальной степени вершин случайного графа''' - это функция <tex>Q(x)</tex>, определённая на <tex>\mathbb{R}</tex> как <tex>P(\xi=x)</tex>, то есть выражающая вероятность того, что максимальная степень вершины <tex>\xi</tex> в графе <tex>G(n, p)</tex> равна <tex>x</tex>
 
}}
 
}}
{{Утверждение
 
|statement=<tex>Q(k) = P(k) \cdot (1 - \sum_{x=k+1}^{n} P(x))</tex>
 
|proof=Будем выводить формулу для <tex>Q(k)</tex> через распределение степеней вершин <tex>P(k)</tex>.
 
  
Максимальная степень вершины равна <tex>k</tex> тогда и только тогда, когда не существует вершины степенью больше <tex>k</tex>. Таким образом, нужно посчитать вероятность события <tex>A: \exists v\in G: \; deg(v) = k \;\&\; !\exists v\in G: \; deg(v) > x</tex>.  
+
Будем выводить формулу для <tex>Q(k)</tex> через распределение степеней вершин <tex>P(k)</tex>.
 +
 
 +
Максимальная степень вершины равна <tex>k</tex> тогда и только тогда, когда не существует вершины степенью больше <tex>k</tex>. Таким образом, нужно посчитать вероятность события <tex>A: \exists v: \; deg(v) = k \;\&\; !\exists v: \; deg(v) > x</tex>.  
  
 
<tex>P(\exists v: \; deg(v) = k) = P(k)</tex>
 
<tex>P(\exists v: \; deg(v) = k) = P(k)</tex>
  
<tex>P(k)</tex> - вероятность того, что вершина имеет степень <tex>k</tex>. Тогда вероятность того, что имеет одну из степеней <tex>1...k</tex> - <tex>\sum_{x=1}^{k}P(x)</tex>. Нам нужно обратное событие, при наступлении которого вершина имеет степень больше <tex>k</tex>. Его вероятность равна <tex>1 - \sum_{x=1}^{k} P(x)</tex>.
+
<tex>P(k)</tex> - вероятность того, что вершина имеет степень <tex>k</tex>. Тогда вероятность того, что имеет одну из степеней <tex>1...k</tex> - <tex>\sum_{x=1}^{k}P(x)</tex>. Нам нужно обратное событие, при наступлении которого вершина имеет степень больше <tex>k</tex>. Его вероятность равна <tex>1 - \sum_{x=1}^{k}P(x)</tex>.
  
<tex>P(!\exists v: \; deg(v) > k) = 1 - \sum_{x=1}^{k} P(x)</tex>
+
<tex>P(!\exists v: \; deg(v) > k) = 1 - \sum_{x=k+1}^{n} P(x)</tex>
  
События независимы, поэтому получаем: <tex>Q(k) = P(k) \cdot (1 - \sum_{x=1}^{k} P(x))</tex>
+
События независимы, поэтому получаем: <tex>Q(k) = P(k) \cdot (1 - \sum_{x=k+1}^{n} P(x))</tex>
}}
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)