Редактирование: Случайные графы
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 17: | Строка 17: | ||
== Существование треугольников в случайном графе == | == Существование треугольников в случайном графе == | ||
{{Теорема | {{Теорема | ||
− | |statement=Если <tex>p(n) = o(\dfrac{1}{n})</tex>, то <tex>G(n, p)</tex> | + | |statement=Если <tex>p(n) = o(\dfrac{1}{n})</tex>, то <tex>G(n, p)</tex> а.п.н не содержит треугольников. '''''Лучше не сокращать а.п.н, я думаю, или в скобочках разок написать, что это''''' |
|proof= | |proof= | ||
Пусть <tex>T</tex> {{---}} число треугольников в графе, <tex>T_{i,j,k}</tex> {{---}} индикаторная случайная величина, равная <tex>1</tex>, если вершины <tex>i</tex>, <tex>j</tex> и <tex>k</tex> образуют треугольник. | Пусть <tex>T</tex> {{---}} число треугольников в графе, <tex>T_{i,j,k}</tex> {{---}} индикаторная случайная величина, равная <tex>1</tex>, если вершины <tex>i</tex>, <tex>j</tex> и <tex>k</tex> образуют треугольник. |