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