4551
правка
Гамильтоновы циклы в случайных графах пересечений: различия между версиями
Перейти к навигации
Перейти к поиску
Гамильтоновы циклы в случайных графах пересечений (посмотреть исходный код)
Версия от 11:48, 3 мая 2015
, 3 мая 2015→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
Рассмотрим экземпляр <math>G_{n,m,p} \;</math>; какова вероятность, что при конкретных значениях параметров n, m и p этот экземпляр будет гамильтоновым графом? Если выразить параметр p модели в виде функции от n и m, то в работе [2] можно найти пороговую функцию P(n, m) для свойства графа «содержит гамильтонов цикл»; иначе говоря, функция P(n, m) is определяется следующим образом: | Рассмотрим экземпляр <math>G_{n,m,p} \;</math>; какова вероятность, что при конкретных значениях параметров n, m и p этот экземпляр будет гамильтоновым графом? Если выразить параметр p модели в виде функции от n и m, то в работе [2] можно найти пороговую функцию P(n, m) для свойства графа «содержит гамильтонов цикл»; иначе говоря, функция P(n, m) is определяется следующим образом: | ||
<math>if p(n, m) | <math>if \; p(n, m) \ll P(n, m)</math> | ||
<math>\lim_{n,m \to \infty} \; \mathbf{Pr} [G_{n,m,p} содержит гамильтонов цикл] = 0</math> | <math>\lim_{n,m \to \infty} \; \mathbf{Pr} [G_{n,m,p} содержит гамильтонов цикл] = 0</math> | ||
<math>if p(n, m) | <math>if \; p(n, m) \gg P(n, m)</math> | ||
<math>\lim_{n,m \to \infty} \; \mathbf{Pr} [G_{n,m,p} содержит гамильтонов цикл] = 1 </math> | <math>\lim_{n,m \to \infty} \; \mathbf{Pr} [G_{n,m,p} содержит гамильтонов цикл] = 1 </math> | ||