4551
правка
Гамильтоновы циклы в случайных графах пересечений: различия между версиями
Перейти к навигации
Перейти к поиску
Гамильтоновы циклы в случайных графах пересечений (посмотреть исходный код)
Версия от 12:53, 3 мая 2015
, 3 мая 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 57: | Строка 57: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Пусть <math>m = \lceil n^{\alpha} \rceil</math>, где <math>\alpha \;</math> – фиксированное положительное вещественное число, а <math>C_1 \;</math> и <math>C_2 \;</math> – достаточно большие константы. Если | '''Теорема 1. Пусть <math>m = \lceil n^{\alpha} \rceil</math>, где <math>\alpha \;</math> – фиксированное положительное вещественное число, а <math>C_1 \;</math> и <math>C_2 \;</math> – достаточно большие константы. Если''' | ||
<math>p \ge C_1 \frac{log \; n}{m}</math> для <math>0 < \alpha < 1 \;</math> или <math>p \ge C_2 \sqrt{ \frac{log \; n}{nm} }</math> для <math>\alpha > 1 \;</math>, | <math>p \ge C_1 \frac{log \; n}{m}</math> для <math>0 < \alpha < 1 \;</math> или <math>p \ge C_2 \sqrt{ \frac{log \; n}{nm} }</math> для <math>\alpha > 1 \;</math>, | ||
тогда почти все <math>G_{n,m,p} \;</math> являются гамильтоновыми. Границы являются асимптотически плотными. | '''тогда почти все <math>G_{n,m,p} \;</math> являются гамильтоновыми. Границы являются асимптотически плотными.''' | ||
Заметим, что теорема ничего не говорит о случае <math>m = n \;</math>, т.е. <math>\alpha = 1 \;</math>. | Заметим, что теорема ничего не говорит о случае <math>m = n \;</math>, т.е. <math>\alpha = 1 \;</math>. | ||