4446
правок
Гамильтоновы циклы в случайных графах пересечений: различия между версиями
Материал из WEGA
Гамильтоновы циклы в случайных графах пересечений (посмотреть исходный код)
Версия от 11:38, 3 мая 2015
, 3 мая 2015нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 7: | Строка 7: | ||
Рассмотрим модель случайных графов, в которых каждая вершина случайным и независимым от других вершин образом выбирает из универсального множества членов своего соответствующего множества. Созданное вероятностное пространство представляет собой пространство случайных графов пересечений <math>G_{n,m,p} \;</math>, где n – количество вершин, m – мощность универсального множества элементов, а p – для каждой вершины – вероятность выбора ею элемента из универсального множества. Модель случайных графов пересечений была впервые предложена в работе [] Каронски, Шейнерманом и Сингер-Коэном. Строгое определение модели случайных графов пересечений выглядит следующим образом: | Рассмотрим модель случайных графов, в которых каждая вершина случайным и независимым от других вершин образом выбирает из универсального множества членов своего соответствующего множества. Созданное вероятностное пространство представляет собой пространство случайных графов пересечений <math>G_{n,m,p} \;</math>, где n – количество вершин, m – мощность универсального множества элементов, а p – для каждой вершины – вероятность выбора ею элемента из универсального множества. Модель случайных графов пересечений была впервые предложена в работе [4] Каронски, Шейнерманом и Сингер-Коэном. Строгое определение модели случайных графов пересечений выглядит следующим образом: | ||
Определение 1. Пусть n и m – целые положительные числа и 0 < p < 1. Случайный граф пересечений | Определение 1. Пусть n и m – целые положительные числа и 0 < p < 1. Случайный граф пересечений <math>G_{n,m,p} \;</math> представляет собой вероятностное пространство над множеством графов на множестве вершин f1..: ; ng, где каждой вершине присвоено случайное подмножество с фиксированным числом элементов m. Между двумя вершинами образуется ребро, если их множества имеют хотя бы один общий элемент. Каждое случайное подмножество, присвоенное вершине, определяется соотношением | ||
Pr [вершина i выбирает элемент j] = p, | Pr [вершина i выбирает элемент j] = p, | ||
причем эти события взаимно независимы. | причем эти события взаимно независимы. | ||
| Строка 21: | Строка 21: | ||
Рассмотрим экземпляр | Рассмотрим экземпляр <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) | if p(n; m) «: P(n; m) | ||
lim Pr \Gn m p Contains Hamilton cyclel = 0 | lim Pr \Gn m p Contains Hamilton cyclel = 0 | ||
| Строка 33: | Строка 33: | ||
Если параметр m в | Если параметр m в <math>G_{n,m,p} \;</math> очень мал в сравнении с n, модель не представляет особенного интереса; если же m значительно больше n, то поведение <math>G_{n,m,p} \;</math> становится очень похожим на поведение модели случайных графов Эрдеша-Реньи [ ]. Если взять m = \na~\ для фиксированного вещественного значения a > 0, то можно наблюдать некоторое отклонение от стандартных моделей и естественный переход от разреженных графов к плотным. Таким образом, будем предполагать, что параметр m имеет вид m = \na] для некоторого фиксированного вещественного a. | ||
Доказательство существования гамильтонова цикла в графе | Доказательство существования гамильтонова цикла в графе <math>G_{n,m,p} \;</math> основано главным образом на установлении отношения стохастического порядка между моделью <math>G_{n,m,p} \;</math> и моделью случайных графов Эрдеша-Реньи Erdos-Renyi Gn>p. | ||
| Строка 59: | Строка 59: | ||
== Применение == | == Применение == | ||
Модель случайных графов Эрдеша-Реньи, Gn;p, широко изучалась в информатике, поскольку она предлагает полезную структуру для изучения таких практических задач, как «надежные сетевые вычисления», а также представляет собой «типичный пример» графа и в силу этого используется для анализа графовых алгоритмов в среднем. Однако простота модели Gn;p означает, что она неспособна удовлетворительно отобразить многие практические задачи информатики – главным образом потому, что независимые граничные события в большинстве задач не слишком оправданны. К примеру, рассмотрим граф, вершины которого представляют множество объектов, расположенных в конкретной географической области или движущихся туда, а ребра – линии радиосвязи. Мы ожидаем, что в таком графе две вершины u и w с большей вероятностью являются смежными, чем любая другая произвольная пара вершин, если обе они смежны некоторой третьей вершине v. Даже эпидемиологические феномены (такие как распространение заболеваний) более точно описываются этой моделью случайных графов пересечений, учитывающей близость расположения. Среди прочих приложений можно отметить «забывчивое» распределение ресурсов в дистрибутивной среде, взаимодействие мобильных агентов, перемещающихся по сети, и т.д. | Модель случайных графов Эрдеша-Реньи, 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 модели. | ||
