Книга: Кому нужна математика? Понятная книга о том, как устроен цифровой мир
Назад: Случайные графы
Дальше: Фазовый переход
Результат Эрдеша – Реньи
В связи с устойчивостью интернета нас интересует вопрос о связности случайного графа. Граф называется связным, если между двумя любыми его вершинами можно пройти по цепочке ребер, то есть все узлы связаны друг с другом. Оба графа на рис. 4.4 – связные. На рис. 4.5 мы сделали их несвязными, удалив по два ребра.
Рис. 4.5. Слева: мини-сеть в виде графа; каналы 1–2 и 1–3 недоступны; граф несвязный, из вершины 1 нельзя попасть в вершины 2 и 3. Справа: социальная сеть в виде графа; пользователь 1 не знаком с пользователями 5 и 6; граф несвязный; нет цепочки знакомых между пользователями 5, 6 и остальными
Эрдеш и Реньи задались вопросом: при какой вероятности помех сеть заданного размера остается связной? Результат получился поразительным! Оказывается, в больших сетях связность сохраняется даже при повышенной вероятности помех.
Например, возьмем сеть из 100 связанных между собой компьютеров. Получается, что каждый отдельный канал может быть недоступен с вероятностью аж 86 %, тем не менее сеть останется связной с вероятностью как минимум… 99 %! Эта ситуация изображена на рис. 4.6: 86 % из всех возможных линий отсутствует, однако сразу видно, что из любого узла можно добраться до любого другого.
Рис. 4.6. Сеть из 100 компьютеров в виде графа. Вероятность недоступности канала 86 %
А сеть из 1000 узлов – это и вовсе нечто фантастическое. Канал связи может быть недоступен с вероятностью 98 %, а связность сохраняется с вероятностью 99,9 %! Чем больше сеть, тем сильнее результат.
В табл. 4.2 мы приводим результаты для сетей разных размеров. Легко заметить, что число в самой правой колонке не что иное, как
Таблица 4.2. Результат Эрдеша – Реньи
Ниже во врезке приведена более общая математическая формулировка результата. Этот текст рассчитан на уровень средней школы, но если вы не хотите вдаваться в подробности, можете его пропустить.
Простейший вариант теоремы Эрдеша – Реньи
Символ ln(n) означает натуральный логарифм числа n. В данном случае нам важно только то, что если n увеличивается, то ln(n) тоже увеличивается, но очень медленно.Теорема Эрдеша – Реньи. Допустим, сеть состоит из n узлов. Предположим, что связь между любыми двумя узлами недоступна с вероятностью q(n) независимо от других связей в сети. Если
то связность сети сохраняется с вероятностью не меньше, чем
В табл. 4.2 во втором и третьем столбце все значения умножены на 100 %. Во втором столбце указаны значения, полученные с помощью формулы (4.1). Поскольку ln(n) растет гораздо медленнее, чем n, то допустимая вероятность помех увеличивается. В третьем столбце – значения (4.2), то есть
Для многих приложений важно умение работать с сетями, в которых изначально присутствуют не все возможные связи. Например, таковы сети автомобильных дорог, социальные сети и тот же интернет.
Надежность сети, по сути, и есть та вероятность уничтожения отдельной связи в ней, начиная с которой общая связность маловероятна. Для описанной выше ситуации надежность исключительно высока, и это строго доказанный результат.
Назад: Случайные графы
Дальше: Фазовый переход
