4551
правка
Гамильтоновы циклы в случайных графах пересечений: различия между версиями
Перейти к навигации
Перейти к поиску
Гамильтоновы циклы в случайных графах пересечений (посмотреть исходный код)
Версия от 11:36, 3 мая 2015
, 3 мая 2015→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Порог появления гамильтоновых циклов в случайных графах п…») |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
Рассмотрим модель случайных графов, в которых каждая вершина случайным и независимым от других вершин образом выбирает из универсального множества членов своего соответствующего множества. Созданное вероятностное пространство представляет собой пространство случайных графов пересечений | Рассмотрим модель случайных графов, в которых каждая вершина случайным и независимым от других вершин образом выбирает из универсального множества членов своего соответствующего множества. Созданное вероятностное пространство представляет собой пространство случайных графов пересечений <math>G_{n,m,p} \;</math>, где n – количество вершин, m – мощность универсального множества элементов, а p – для каждой вершины – вероятность выбора ею элемента из универсального множества. Модель случайных графов пересечений была впервые предложена в работе [] Каронски, Шейнерманом и Сингер-Коэном. Строгое определение модели случайных графов пересечений выглядит следующим образом: | ||
| Строка 46: | Строка 46: | ||
Отношение стохастического порядка между двумя моделями случайных графов устанавливается следующим образом: если A – возрастающее свойство графа, тогда имеет место | Отношение стохастического порядка между двумя моделями случайных графов устанавливается следующим образом: если A – возрастающее свойство графа, тогда имеет место | ||
где p = f(p). Свойство графа A является возрастающим в том и только том случае, что если A выполняется для графа G(V, E), то A выполняется для любого графа G(v, E0): E0 2 E. | где p = f(p). Свойство графа A является возрастающим в том и только том случае, что если A выполняется для графа G(V, E), то A выполняется для любого графа G(v, E0): E0 2 E. | ||
== Основные результаты == | == Основные результаты == | ||