4551
правка
Связность и отказоустойчивость в случайных регулярных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Связность и отказоустойчивость в случайных регулярных графах (посмотреть исходный код)
Версия от 03:23, 24 января 2013
, 24 января 2013→Лемма о конфигурации, лемма о переводе
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 27: | Строка 27: | ||
== Лемма о конфигурации, лемма о переводе == | == Лемма о конфигурации, лемма о переводе == | ||
С технической точки зрения делать какие-либо утверждения о случайных регулярных графах не так просто, как в случае | С технической точки зрения делать какие-либо утверждения о случайных регулярных графах не так просто, как в случае <math>G_{n,p}</math>, в силу стохастических зависимостей от существования дуг, связанных с регулярностью. Введенная Боллобасом [2, 3] нотация [[конфигурация|конфигурации]] предназначена для перевода операторов для случайных регулярных графов в операторы для соответствующих конфигураций, которые не содержат зависимостей между дугами в силу регулярности и с которыми поэтому намного проще работать. | ||
'''Определение 2 (Боллобас, [3])'''. Пусть <math>w = \cup^n_{j=1} w_j</math> – фиксированное множество <math>2m = \sum^n_{j=1} d_j</math> помеченных вершин, где <math>|w_j| = d_j \; </math>. Конфигурация F представляет собой разбиение w на m пар вершин, называемых дугами F. | |||
Пусть дана конфигурация F. Пусть <math>\theta\ (F)</math> – (мульти)граф с множеством вершин V, в котором (i, j) является дугой в том и только том случае, если в F имеется пара (дуга), имеющая один элемент в <math>w_i \; </math>, а другой – в <math>w_j \; </math>. Заметим, что каждый регулярный граф <math>G \in G^r_n</math> имеет форму <math>\theta\ (F)</math> в точности для <math>(r!)^n \; </math> конфигураций. Однако не каждая конфигурация F с <math>d_j = r \; </math> для всех j соответствует ситуации <math>G \in G^r_n</math>, поскольку F может содержать дугу, полностью находящуюся в некотором <math>w_j \; </math>, либо параллельные дуги, связывающие <math>w_i \; </math> и <math>w_j \; </math>. | |||
Пусть ' – множество всех конфигураций F, а Grn – множество всех регулярных графов. Учитывая свойство Q С Grn, пусть Q* С ф, такое, что Q* \ 6»-1(G;) = ^(Q). В результате оценки вероятности возможных циклов длины 1 (петля) и 2 (цикл) между парами wi; wj в 9(F) получается следующая лемма. | Пусть ' – множество всех конфигураций F, а Grn – множество всех регулярных графов. Учитывая свойство Q С Grn, пусть Q* С ф, такое, что Q* \ 6»-1(G;) = ^(Q). В результате оценки вероятности возможных циклов длины 1 (петля) и 2 (цикл) между парами wi; wj в 9(F) получается следующая лемма. | ||