4551
правка
Гамильтоновы циклы в случайных графах пересечений: различия между версиями
Перейти к навигации
Перейти к поиску
м
Гамильтоновы циклы в случайных графах пересечений (посмотреть исходный код)
Версия от 13:29, 3 мая 2015
, 3 мая 2015→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
Отношение стохастического порядка между двумя моделями случайных графов устанавливается следующим образом: если <math>\mathcal{A} \;</math> – возрастающее свойство графа, тогда имеет место соотношение | Отношение стохастического порядка между двумя моделями случайных графов устанавливается следующим образом: если <math>\mathcal{A} \;</math> – возрастающее свойство графа, тогда имеет место соотношение | ||
<math>\mathbf{Pr} [G_{n, \hat p} \in \mathcal{A}] \le \mathbf{Pr} [G_{n,m,p} \in \mathcal{A}]</math> | <math>\mathbf{Pr} [G_{n, \hat p} \in \mathcal{A}] \le \mathbf{Pr} [G_{n,m,p} \in \mathcal{A}]</math>, | ||
где <math>\hat p = f(p)</math>. Свойство графа <math>\mathcal{A} \;</math> является возрастающим в том и только том случае, что если <math>\mathcal{A} \;</math> выполняется для графа <math>G(V, E) \;</math>, то <math>\mathcal{A} \;</math> выполняется для любого графа <math>G(v, E') \; </math>: <math>E' \supseteq E \;</math>. | где <math>\hat p = f(p)</math>. Свойство графа <math>\mathcal{A} \;</math> является возрастающим в том и только том случае, что если <math>\mathcal{A} \;</math> выполняется для графа <math>G(V, E) \;</math>, то <math>\mathcal{A} \;</math> выполняется для любого графа <math>G(v, E') \; </math>: <math>E' \supseteq E \;</math>. | ||