(←) предыдущая запись ; следующая запись (→)
образовательное, ссылки_вовне, размышления
Ася рассказала, что ей вместо пазла досталась половина пазла. Половина пазла — это интересный математический объект. Например, можно взять кусочки в шахматном порядке, и тогда в пазле не будет ни одной связной компоненты, состоящей более чем из одного кусочка. Но чтобы так получилось нужно специально постараться. Если просто взять коробку, хорошо её потрясти и случайным образом выкинуть половину, наверняка пазл получится не таким. В нём будут и большие дыры, и мелкие дырочки, но в целом он окажется связным. Я так вижу.
Математики такие странные люди, что уже придумали науку почти про это. Называется «теория случайных графов».
Представьте, что у вас есть множество вершин, причём каждая пара вершин может соединяться ребром (такую штуку называют графом). Графы выступают удачной моделью для множества понятий. Например, карта метрополитена — граф. Вершинами являются станции, а рёбрами — перегоны или переходы. Лабиринт тоже легко представить в виде графа. Вершинами являются свободные клеточки, а рёбра соединяют соседние клеточки, между которыми нет препятствий.
И пазл — это тоже граф, только очень простой. Каждая деталька является вершиной. А рёбра соединяют те детальки, которые в пазле должны быть соединены. То есть у каждой вершины (кроме тех, что по краям) по четыре ребра.
Что такое случайный граф? Это граф, в котором рёбра между вершинами расставлены не с умыслом, а как получилось. Возьмём, например, десять вершин и соединим их пятнадцатью рёбрами (из 45 возможных). Можно, например, каждое потенциальное ребро либо взять с вероятностью p = 1/3, либо отбросить с вероятностью 2/3. Тогда как раз из 45 рёбер получится в среднем 15.
Случайные графы нашли своё применение в сельском хозяйстве. Например, их можно использовать, чтобы изучать связность (= устойчивость) интернета и любых других коммуникаций.
Случайные графы ведут себя необычно. Возьмём теперь БОЛЬШОЙ граф, из целых n вершин. При этом каждое ребро «принимается» в граф с вероятностью p. Попытаемся теперь понять, будет ли связен получившийся граф (граф называется связным, если в нём от каждой вершины можно по рёбрам дойти до любой другой).
Понятно, что если вероятность p большая, т.е. близкая к 1, то случайный граф скорее всего будет связен. А если p маленькая, то наоборот.
Так вот, оказывается, что есть чёткая граница между связными и несвязными графами. Если p = с⋅log(n)/n, и при этом c > 1 то почти любой такой случайный граф будет связен, а если c < 1, то наоборот: почти любой такой граф будет состоять из нескольких компонент. Что в этом удивительного? А то, что в этой точке случается фазовый переход: до неё почти все графы были несвязными, а после почти все — связные. Нет такого, что происходит плавное нарастание — типа вот при таком c будет 5% связных графов, а при таком — 25%. Всё происходит скачком. Вернее двумя скачками, потому что есть ровно одна точка посередине между этими двумя позициями. Так при c = 1, доля связных графов будет 1/e среди всех случайных графов.
Если вы хотите уличить меня в неточности формулировок, почитайте книжку Райгородского про модели случайных графов, он большой специалист в этом. И очень классный лектор и популяризатор.
Кстати, наша простейшая схема построения случайного графа у математиков пафосно называется «моделью Эрдёша-Реньи». И это явно сделано чтобы запугать непосвящённых.
(1/2)