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

Модель случайных графов Эрдеша-Реньи, Gn;p, широко изучалась в информатике, поскольку она предлагает полезную структуру для изучения таких практических задач, как «надежные сетевые вычисления», а также представляет собой «типичный пример» графа и в силу этого используется для анализа графовых алгоритмов в среднем. Однако простота модели Gn;p означает, что она неспособна удовлетворительно отобразить многие практические задачи информатики – главным образом потому, что независимые граничные события в большинстве задач не слишком оправданны. К примеру, рассмотрим граф, вершины которого представляют множество объектов, расположенных в конкретной географической области или движущихся туда, а ребра – линии радиосвязи. Мы ожидаем, что в таком графе две вершины u и w с большей вероятностью являются смежными, чем любая другая произвольная пара вершин, если обе они смежны некоторой третьей вершине v. Даже эпидемиологические феномены (такие как распространение заболеваний) более точно описываются этой моделью случайных графов пересечений, учитывающей близость расположения. Среди прочих приложений можно отметить «забывчивое» распределение ресурсов в дистрибутивной среде, взаимодействие мобильных агентов, перемещающихся по сети, и т.д.

Модель случайных графов пересечений <math>G_{n,m,p} \;</math> была впервые предложена Каронски, Шейнерманом и Сингер-Коэном в работе [], в которой они изучали эволюцию случайных графов пересечений при помощи исследования порогов появления и исчезновения малых порожденных подграфов. Кроме того, Филл, Шейнерман и Сингер-Коэн доказали [ ] теорему эквивалентности, связанную с эволюцией <math>G_{n,m,p} \;</math> и Gn;p; в частности, они доказали, что в случае m = na, где a > 6, вариационное расстояние между переменными случайного графа имеет предел, равный 0. Николетсис, Раптопулос и Спиракис [8] исследовали существование и эффективное алгоритмическое построение близких к оптимальным независимых множеств в случайных графах пересечений. Старк [ ] изучал степени вершин в случайных графах пересечений. Однако после выхода работы [2] Спиракис и Раптопулос в [ ] предложили алгоритмы для построения гамильтоновых циклов в экземплярах <math>G_{n,m,p} \;</math> для значений p, превышающих порог гамильтоновости. Наконец, Николетсис и коллеги [ ] изучали продолжительность смешивания и продолжительность покрытия в связи с изменением параметра p модели.