Гамильтоновы циклы в случайных графах пересечений
Ключевые слова и синонимы
Порог появления гамильтоновых циклов в случайных графах пересечений; отношения стохастического порядка между моделью случайных графов Эрдеша-Реньи и случайными графами пересечений
Постановка задачи
Эдвард Марчевский доказал, что каждый граф может быть представлен в виде списка множеств, в котором каждая вершина соответствует множеству, а ребра – непустому пересечению множеств. Естественным образом возникает вопрос: графы какого типа будут получаться чаще всего при случайной генерации таких списков?
Рассмотрим модель случайных графов, в которых каждая вершина случайным и независимым от других вершин образом выбирает из универсального множества членов своего соответствующего множества. Созданное вероятностное пространство представляет собой пространство случайных графов пересечений [math]\displaystyle{ G_{n,m,p} \; }[/math], где n – количество вершин, m – мощность универсального множества элементов, а p – для каждой вершины – вероятность выбора ею элемента из универсального множества. Модель случайных графов пересечений была впервые предложена в работе [4] Каронски, Шейнерманом и Сингер-Коэном. Строгое определение модели случайных графов пересечений выглядит следующим образом:
Определение 1. Пусть n и m – целые положительные числа и [math]\displaystyle{ 0 \le p \le 1 }[/math]. Случайный граф пересечений [math]\displaystyle{ G_{n,m,p} \; }[/math] представляет собой вероятностное пространство над множеством графов на множестве вершин {1, ..., n}, где каждой вершине присвоено случайное подмножество с фиксированным числом элементов m. Между двумя вершинами образуется ребро, если их множества имеют хотя бы один общий элемент. Каждое случайное подмножество, присвоенное вершине, определяется соотношением
Pr [вершина i выбирает элемент j] = p,
причем эти события взаимно независимы.
Типичным вопросом относительно графа является наличие в нем цикла – множества ребер, формирующих путь, первая и последняя вершина которого совпадают, проходящий по всем вершинам графа ровно один раз. Такой цикл называется гамильтоновым циклом, а содержащий его граф – гамильтоновым графом.
Определение 2. Рассмотрим неориентированный граф G = (V, E), где V – множество вершин, а E – множество ребер. Этот граф содержит гамильтонов цикл в том и только том случае, когда имеется простой цикл, содержащий каждую вершину V.
Рассмотрим экземпляр [math]\displaystyle{ G_{n,m,p} \; }[/math]; какова вероятность, что при конкретных значениях параметров n, m и p этот экземпляр будет гамильтоновым графом? Если выразить параметр p модели в виде функции от n и m, то в работе [2] можно найти пороговую функцию P(n, m) для свойства графа «содержит гамильтонов цикл»; иначе говоря, функция P(n, m) is определяется следующим образом:
[math]\displaystyle{ if \; p(n, m) \ll P(n, m) }[/math]
[math]\displaystyle{ \lim_{n,m \to \infty} \; \mathbf{Pr} [G_{n,m,p} содержит гамильтонов цикл] = 0 }[/math]
[math]\displaystyle{ if \; p(n, m) \gg P(n, m) }[/math]
[math]\displaystyle{ \lim_{n,m \to \infty} \; \mathbf{Pr} [G_{n,m,p} содержит гамильтонов цикл] = 1 }[/math]
Если такое свойство графа, как «содержит гамильтонов цикл», выполняется с вероятностью, стремящейся к 1 (или 0), в то время как n и m стремятся к бесконечности, то мы можем утверждать, что свойство выполняется (или не выполняется) «почти наверное» или «почти заведомо».
Если параметр m в [math]\displaystyle{ G_{n,m,p} \; }[/math] очень мал в сравнении с n, модель не представляет особенного интереса; если же m значительно больше n, то поведение [math]\displaystyle{ G_{n,m,p} \; }[/math] становится очень похожим на поведение модели случайных графов Эрдеша-Реньи [3]. Если взять [math]\displaystyle{ m = \lceil n^{\alpha} \rceil }[/math] для фиксированного вещественного значения [math]\displaystyle{ \alpha \gt 0 \; }[/math], то можно наблюдать некоторое отклонение от стандартных моделей и естественный переход от разреженных графов к плотным. Таким образом, будем предполагать, что параметр m имеет вид m = \na] для некоторого фиксированного вещественного [math]\displaystyle{ \alpha \; }[/math].
Доказательство существования гамильтонова цикла в графе [math]\displaystyle{ G_{n,m,p} \; }[/math] основано главным образом на установлении отношения стохастического порядка между моделью [math]\displaystyle{ G_{n,m,p} \; }[/math] и моделью случайных графов Эрдеша-Реньи [math]\displaystyle{ G_{n, \hat p} }[/math].
Определение 3. Пусть n – целое положительное число и [math]\displaystyle{ 0 \le \hat p \le 1 \; }[/math]. Случайный граф [math]\displaystyle{ G_{n, \hat p} }[/math] представляет собой вероятностное пространство над множеством графов на множестве вершин {1, ..., n}, определенное соотношением
[math]\displaystyle{ \mathbf{Pr} [i,j] = \hat p }[/math]
причем эти события взаимно независимы.
Отношение стохастического порядка между двумя моделями случайных графов устанавливается следующим образом: если [math]\displaystyle{ \mathcal{A} \; }[/math] – возрастающее свойство графа, тогда имеет место соотношение
[math]\displaystyle{ \mathbf{Pr} [G_{n, \hat p} \in \mathcal{A}] \le \mathbf{Pr} [G_{n,m,p} \in \mathcal{A}] }[/math]
где [math]\displaystyle{ \hat p = f(p) }[/math]. Свойство графа [math]\displaystyle{ \mathcal{A} \; }[/math] является возрастающим в том и только том случае, что если [math]\displaystyle{ \mathcal{A} \; }[/math] выполняется для графа [math]\displaystyle{ G(V, E) \; }[/math], то [math]\displaystyle{ \mathcal{A} \; }[/math] выполняется для любого графа [math]\displaystyle{ G(v, E') \; }[/math]: [math]\displaystyle{ E' \supseteq E \; }[/math].
Основные результаты
Теорема 1. Пусть [math]\displaystyle{ m = \lceil n^{\alpha} \rceil }[/math], где [math]\displaystyle{ \alpha \; }[/math] – фиксированное положительное вещественное число, а [math]\displaystyle{ C_1 \; }[/math] и [math]\displaystyle{ C_2 \; }[/math] – достаточно большие константы. Если
[math]\displaystyle{ p \ge C_1 \frac{log \; n}{m} }[/math] для [math]\displaystyle{ 0 \lt \alpha \lt 1 \; }[/math] или [math]\displaystyle{ p \ge C_2 \sqrt{ \frac{log \; n}{nm} } }[/math] для [math]\displaystyle{ \alpha \gt 1 \; }[/math],
тогда почти все [math]\displaystyle{ G_{n,m,p} \; }[/math] являются гамильтоновыми. Границы являются асимптотически плотными.
Заметим, что теорема ничего не говорит о случае [math]\displaystyle{ m = n \; }[/math], т.е. [math]\displaystyle{ \alpha = 1 \; }[/math].
Применение
Модель случайных графов Эрдеша-Реньи, [math]\displaystyle{ G_{n,p} \; }[/math], широко изучалась в информатике, поскольку она предлагает полезную структуру для изучения таких практических задач, как «надежные сетевые вычисления», а также представляет собой «типичный пример» графа и в силу этого используется для анализа графовых алгоритмов в среднем. Однако простота модели [math]\displaystyle{ G_{n,p} \; }[/math] означает, что она неспособна удовлетворительно отобразить многие практические задачи информатики – главным образом потому, что независимые граничные события в большинстве задач не слишком оправданны. К примеру, рассмотрим граф, вершины которого представляют множество объектов, расположенных в конкретной географической области или движущихся туда, а ребра – линии радиосвязи. Мы ожидаем, что в таком графе две вершины u и w с большей вероятностью являются смежными, чем любая другая произвольная пара вершин, если обе они смежны некоторой третьей вершине v. Даже эпидемиологические феномены (такие как распространение заболеваний) более точно описываются этой моделью случайных графов пересечений, учитывающей близость расположения. Среди прочих приложений можно отметить «забывчивое» распределение ресурсов в дистрибутивной среде, взаимодействие мобильных агентов, перемещающихся по сети, и т.д. Модель случайных графов пересечений [math]\displaystyle{ G_{n,m,p} \; }[/math] была впервые предложена Каронски, Шейнерманом и Сингер-Коэном в работе [4], в которой они изучали эволюцию случайных графов пересечений при помощи исследования порогов появления и исчезновения малых порожденных подграфов. Кроме того, Филл, Шейнерман и Сингер-Коэн доказали [3] теорему эквивалентности, связанную с эволюцией [math]\displaystyle{ G_{n,m,p} \; }[/math] и [math]\displaystyle{ G_{n,p} \; }[/math]; в частности, они доказали, что в случае [math]\displaystyle{ m = n^{\alpha} \; }[/math], где [math]\displaystyle{ \alpha \gt 6 \; }[/math], вариационное расстояние между переменными случайного графа имеет предел, равный 0. Николетсис, Раптопулос и Спиракис [8] исследовали существование и эффективное алгоритмическое построение близких к оптимальным независимых множеств в случайных графах пересечений. Старк [12] изучал степени вершин в случайных графах пересечений. Однако после выхода работы [2] Спиракис и Раптопулос в [11] предложили алгоритмы для построения гамильтоновых циклов в экземплярах [math]\displaystyle{ G_{n,m,p} \; }[/math] для значений p, превышающих порог гамильтоновости. Наконец, Николетсис и коллеги [7] изучали продолжительность смешивания и продолжительность покрытия в связи с изменением параметра p модели.
Открытые вопросы
Как и во многих других случайных структурах, например, [math]\displaystyle{ G_{n,p} \; }[/math] и random formulae, свойства случайных графов пересечений также имеют пороговое поведение. До настоящего момента пороговое поведение исследовалось для появления порожденных подграфов и гамильтоновости.
Также можно изучать такие аспекты случайных графов пересечений, как поведение модели относительно связности, т.е. формирование путей и формирование гигантских компонент. Кроме того, представляет значительный интерес изменение продолжительности смешивания и продолжительности покрытия в зависимости от изменения параметра p модели.
См. также
Литература
1. Alon, N., Spencer, J.H.: The Probabilistic Method. 2nd edn. Wiley, New York (2000)
2. Efthymiou, C., Spirakis, P.G.: On the Existence of Hamilton Cycles in Random Intersection Graphs. In: Proc. of the 32nd ICALP. LNCS, vol. 3580, pp. 690-701. Springer, Berlin/Heidelberg (2005)
3. Fill, J.A., Scheinerman, E.R., Singer-Cohen, K.B.: Random intersection graphs when m = !(n): an equivalence theorem relating the evolution of the G(n; m; p) and G(n; p) models. Random Struct. Algorithms 16,156-176 (2000)
4. Karonski, M., Scheinerman, E.R., Singer-Cohen, K.: On Random Intersection Graphs: The Subgraph Problem. Comb. Probab. Comput. 8,131-159(1999)
5. Komlos, J., Szemeredi, E.: Limit Distributions for the existence of Hamilton cycles in a random graph. Discret. Math. 43,55-63 (1983)
6. Korshunov, A.D.: Solution of a problem of P. Erdos and A. Renyion Hamilton Cycles in non-oriented graphs. Metody Diskr.Anal. TeoriyUpr.Syst. Sb.TrubovNovosibrirsk31,17-56 (1977)
7. Nikoletseas, S., Raptopoulos, C., Spirakis, P.: Expander Properties and the Cover Time of Random Intersection Graphs. In: Proc of the 32nd MFCS, pp. 44-55. Springer, Berlin/Heidelberg (2007)
8. Nikoletseas, S., Raptopoulos, C., Spirakis, P.: The existence and Efficient construction of Large Independent Sets in General Random Intersection Graphs. In: Proc. of the 31 st ICALP. LNCS, vol. 3142, pp. 1029-1040. Springer, Berlin/Heidelberg (2004)
10. Singer, K.: Random Intersection Graphs. Ph. D. thesis, The Johns Hopkins University, Baltimore (1995)
11. Spirakis, P.G. Raptopoulos, C.: Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs. In: Proc. of the 16th ISAAC. LNCS, vol. 3827, pp. 493-504. Springer, Berlin/Heidelberg (2005)
12. Stark, D.: The Vertex Degree Distribution of Random Intersection Graphs. Random Struct. Algorithms 24, 249-258 (2004)