89
правок
Изменения
м
→Графы имеющие диаметр два
== Графы имеющие диаметр два ==
{{Определение
|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>
