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

Рассмотрим модель случайных графов, в которых каждая вершина случайным образом выбирает из универсального множества членов своего соответствующего множества – каждую независимо от других. Созданное вероятностное пространство представляет собой пространство случайных графов пересечений <math>G_{n,m,p} \;</math>, где n – количество вершин, m – мощность универсального множества элементов, а p – для каждой вершины – вероятность выбора ею элемента из универсального множества. Модель случайных графов пересечений была впервые предложена в работе [4] Каронски, Шейнерманом и Сингер-Коэном. Строгое определение модели случайных графов пересечений выглядит следующим образом: