Гамильтоновы циклы в случайных графах пересечений: различия между версиями

Если параметр m в <math>G_{n,m,p} \;</math> очень мал в сравнении с n, модель не представляет особенного интереса; если же m значительно больше n, то поведение <math>G_{n,m,p} \;</math> становится очень похожим на поведение модели случайных графов Эрдеша-Реньи [3]. Если взять <math>m = \lceil n^{\alpha} \rceil</math> для фиксированного вещественного значения <math>\alpha > 0 \;</math>, то можно наблюдать некоторое отклонение от стандартных моделей и естественный переход от разреженных графов к плотным. Таким образом, будем предполагать, что параметр m имеет вид m = \na] для некоторого фиксированного вещественного a.

Доказательство существования гамильтонова цикла в графе <math>G_{n,m,p} \;</math> основано главным образом на установлении отношения стохастического порядка между моделью <math>G_{n,m,p} \;</math> и моделью случайных графов Эрдеша-Реньи Erdos-Renyi Gn>p.

Определение 3. Пусть n – целое положительное число и 0 < p < 1. Случайный граф G(n, p) представляет собой вероятностное пространство над множеством графов на множестве вершин f1..: ; ng, определенное соотношением

Pr [i,j]=p