436
правок
Изменения
м
Пусть дан граф В произвольном графе <tex>G = (V,E)</tex>. Зафиксируем зафиксируем <tex>v_1 \in V</tex>. Пометим ее как активную, а все остальные вершины {{---}} нейтральными. Выберем среди нейтральных вершин всех соседей вершины <tex>v_1</tex>. После этого пометим вершину <tex>v_1</tex> как неактивную , а смежных с ней {{---}} как активных, а все остальные вершины {{---}} нейтральными.
Заметим, что данный Данный процесс очень похож на [[Обход в ширину|поиск в ширину]], данным этим свойством мы воспользуемся позднее.<br>
→Теорема о гигантской компоненте
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.
}}
Снова зафиксируем какую-нибудь активную вершину <tex>v_2</tex>, и повторим процесс. Не меняем , не меняя статус остальных уже активных вершин.
Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины.<br>
Обозначим число активных вершин в момент времени <tex>t</tex> через <tex>Y_t</tex>, число нейтральных вершин {{---}} через <tex>N_t</tex>, а число соседей вершины, которую собираемся пометить как неактивную, {{---}} через <tex>Z_t</tex>. Тогда <tex>Y_0 = 1,Y_t = Y_t−1 + Z_t − 1</tex>. Все введенные величины зависят от графа <tex>G</tex> и от последовательности выбираемых вершин <tex>v_1,\dotsc</tex>.
'''Случай <tex>c < 1</tex>'''.
Положим <tex>t_0=[\beta \ln n]</tex>, где <tex>\beta = \beta(c)</tex> {{---}} константа, которую мы подберем позднеекоторая будет подобрана далее. Нам хочется доказать, что с большой вероятностью каждая из компонент случайного графа имеет размер <tex>\le t_0</tex>.
Но размер компоненты {{---}} это момент вырождения процесса <tex>Y_t</tex> на случайном графе. Значит, интересующее нас утверждение можно записать в следующем виде:
<tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \rightarrow 0, n \rightarrow \infty</tex>
Поскольку <tex>P_{n, p}(\exists v_1 : Y_{t_0} > 0) \le nP_{n, p}(Y_{t_0} \ge 0)</tex>, достаточно найти такое <tex>\beta</tex>, при котором <tex>P_{n, p}(Y_{t_0} > 0) = o\left(\dfracfrac{1}{n}\right).</tex><br> Далее:<br>
<tex>P_{n, p}(Y_{t_0} > 0) = P_{n, p}(\xi_{t_o} > t_0) \thickapprox P_{n, p}(Binomial(n, 1 - (1 - p)^{t_0}) > t_0) \thickapprox</tex><br>
(с учетом асимптотики <tex>1 - (1 - p)^{t_0} \thicksim pt_0) </tex><br>
'''Случай <tex>c > 1</tex>'''.
В данном случае ветвящийся процесс на графе нужно «запускать» не один раз, а многократно. Только так удается доказать, что почти наверняка а.п.н. хотябы в одном запуске возникнет гигантская компонента. Подробности можно найти в <ref name="trueproof" />, мы же лишь поясним, откуда в текущей ситуации появляется константа <tex>\gamma</tex> из формулировки '''предыдущей''' теоремы и почему она совпадает с одноименной константой из той же теоремы. '''Лучше сделать ссылку на прокрутку статьи вверх, но в целом можно забить. Вообще "предыдущая теорема" - не очень хорошая ссылка'''
Чтобы доказать, что есть гигантская компонента, необходимо, чтобы ветвящийся процесс на графе не вырождался даже
при <tex>t \thickapprox \gamma n</tex>. Иными словами, необходимо, чтобыто есть:<br>
<tex>P_{n, p}(Y_{t_0} \le 0)\rightarrow 0, t \thickapprox \gamma n, n \rightarrow \infty</tex>
