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

Определение 1. Пусть n и m – целые положительные числа и 0 < p < 1. Случайный граф пересечений <math>G_{n,m,p} \;</math> представляет собой вероятностное пространство над множеством графов на множестве вершин f1..: ; ng, где каждой вершине присвоено случайное подмножество с фиксированным числом элементов m. Между двумя вершинами образуется ребро, если их множества имеют хотя бы один общий элемент. Каждое случайное подмножество, присвоенное вершине, определяется соотношением

Pr [вершина i выбирает элемент j] = p,

Типичным вопросом относительно графа является наличие в нем цикла – множества ребер, формирующих путь, первая и последняя вершина которого совпадают, проходящий по всем вершинам графа ровно один раз. Такой цикл называется гамильтоновым циклом, а содержащий его граф – гамильтоновым графом.