1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение|neat = 1|definition= '''Модель Эрдёша-Реньи''' (англ. ''Erdős–Rényi model'') {{---}} модель генерации случайных графов, в которой все графы с фиксированным набором вершин и фиксированным набором рёбер одинаково вероятны. Существует два тесно связанных варианта модели: ''биномиальная'' и ''равномерная''.}}
{{Определение
|neat = 1
}}
{{Определение
|definition= Свойство <tex>A</tex> графа <tex>G(n, p(n))</tex> '''асимптотически почти наверное истинно''', если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 1</tex>, где <tex>p(n)</tex> {{---}} вероятность графа <tex>G(n, p)</tex> обладать этим свойством.
}}
{{Определение
|definition= Свойство <tex>A</tex> графа <tex>G(n, p(n))</tex> '''асимптотически почти наверное ложно''', если <tex>\lim\limits_{n \rightarrow \infty} p(n) = 0</tex>, где <tex>p(n)</tex> {{---}} вероятность графа <tex>G(n, p)</tex> обладать этим свойством.
}}
<tex>E[T^2] = E[(\sum\limits_{i, j, k}T_{i, j, k})^2]= E[\sum\limits_{i, j, k}T_{i, j, k})^2] + E[\sum\limits_{i, j, k, a, b, c}T_{i, j, k}T_{a, b, c}] =</tex>
<tex>= E[T] + (C^3_nC^3_{n - 3} + C^3_nC^2_{n - 3})p^6 + 3C^3_n(n - 3)p^5 \sim \dfrac{n^3p^3}{6} + (\dfrac{n^6}{36} + \dfrac{n^5}{4})p^6 + \dfrac{n^4}{2}p^5 \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36} + \dfrac{n^4p^5}{2} \sim \dfrac{n^3p^3}{6} + \dfrac{n^6p^6}{36}</tex>
{{Теорема
|statement=<tex>p = \dfrac{c\ln n}{n}</tex>, тогда при <tex>c < 1</tex> граф а.п.н связен, при <tex>c > 1</tex> граф а.п.н не связен.
}}
== Распределение степеней вершин ==
{{Определение
|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>.
}}
{{Пример
|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>.
}}
{{Утверждение
|statement=Дан случайный граф <tex>G(n, p)</tex> в биноминальной модели. Тогда для него распределение степеней вершин
<p>
<tex>
\begin{equation*}
P(k) = {n-1 \choose k} p^k(1-p)^{n-1-k}
\end{equation*}
</tex>
</p>
|proof=Действительно, если вероятность появления ребра <tex>p</tex>, то вероятность появления ровно <tex>k</tex> рёбер у вершины равна <tex>p^k(1-p)^{n-1-k}</tex>([[схема Бернулли]]). Таких наборов рёбер у одной вершины всего <tex>{n-1 \choose k}</tex>, откуда получаем искомое распределение.
}}
== Распределение максимальной степени вершин ==
{{Определение
|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>.
}}
{{Утверждение
|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>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(!\exists v: \; deg(v) > k) = 1 - \sum_{x=1}^{k} P(x)</tex>
События независимы, поэтому получаем: <tex>Q(k) = P(k) \cdot (1 - \sum_{x=1}^{k} P(x))</tex>
}}
{{Теорема
|id=th1
|statement= Пусть <tex>N_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | N_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>E[N_z ] \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>, то <tex>A</tex> а.п.н ложно.
|proof=
Воспользуемся [[Неравенство Маркова | неравенством Маркова]]:
<tex>P(N_z > 0) = P(N_z \geqslant 1) \leqslant EZ E[N_z] \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
{{Теорема
|id=th2
|statement= Пусть <tex>N_z</tex> {{---}} число объектов в графе <tex>G(n, p)</tex>. <tex>A = \{G | N_z(G) > 0 \}</tex> {{---}} свойство. Тогда, если <tex>EN_z E[N_z] \rightarrow \infty</tex>, при <tex>n \rightarrow \infty</tex>, и <tex>EZE[N_z^2 = ] \leqslant (EZE[N_z])^2(1 + o(1))</tex> то <tex>A</tex> а.п.н истинно.
|proof=
Воспользуемся [[Неравенство Маркова#thCheb | неравенством Чебышева]]:
<tex>P(N_z = 0) = P(N_z \leqslant 0) = P(EN_z E[N_z] - N_z \geqslant EN_zE[N_z]) \leqslant P(|EN_z E[N_z] - N_z| \geqslant EN_zE[N_z]) \leqslant \dfrac{DN_zD[N_z]}{(EN_zE[N_z])^2} \rightarrow 0</tex>, при <tex>n \rightarrow \infty</tex>.
}}
== Графы , имеющие диаметр два =={{Определение|definition=<tex>A</tex> {{---}} некоторое свойство случайного графа. <tex>p</tex> называется '''пороговой функцией''' (англ. ''threshold function''), если граф <tex>G(n, cp)</tex> при <tex>c < 1</tex> а.п.н не имеет такого свойства, а при <tex>c > 1</tex> а.п.н имеет.}}
{{Теорема
|statement=Пусть рассматривается свойство графа иметь диаметр два. Тогда <tex>p = \sqrt{2} \sqrt{\dfrac{\ln n}{n}}</tex> {{---}} порогпороговая функция.'''''что такое порог?'''''
|proof=
Назовем вершины <tex>u</tex> и <tex>v</tex> плохой парой, если кратчайшее расстояние между <tex>dist(u, </tex> и <tex>v) > 2</tex> '''''мб лучше написать про расстояние явно, но думаю, всем будет понятно'''''больше двух. <tex>B_{i, j}</tex> {{---}} индикаторная величина, равная <tex>1</tex>, если <tex>i</tex> и <tex>j</tex> являются плохой парой.
<tex>N_z = \sum\limits_{i, j} B_{i,j}</tex>
<tex>P(B_{i, j}) = (1 - p)(1 - p^2)^{n - 2}</tex>
[[Категория: Дискретная математика и алгоритмы]][[Категория: Теория графов]]
