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

Определение 2. Рассмотрим неориентированный граф G = (V, E), где V – множество вершин, а E – множество ребер. Этот граф содержит гамильтонов цикл в том и только том случае, когда имеется простой цикл, содержащий каждую вершину V.

Рассмотрим экземпляр <math>G_{n,m,p} \;</math>; какова вероятность, что при конкретных значениях параметров n, m и p этот экземпляр будет гамильтоновым графом? Если выразить параметр p модели в виде функции от n и m, то в работе [ ] можно найти пороговую функцию P(n; m) для свойства графа «содержит гамильтонов цикл»; иначе говоря, функция P(n; m) is определяется следующим образом:

if p(n; m) «: P(n; m)

lim    Pr \Gn m p Contains Hamilton cyclel = 0

if p(n; m) » P(n; m)

lim    Pr \Gn m n Contains Hamilton cyclel = 1

n,m^s-oo        L      >    >r J