MakarovSuites
Русский
EnglishDeutschРусскийУкраїнськаFrançaisEspañolItalianoPolski
Связь и лицензии

Math

Перколяция

Вход, выход и один образец случайной решётки: предскажи, при каком p этот образец впервые пропустит поток, подними p или открой отдельные узлы руками и смотри, как растёт достижимая область, — потом прогони много образцов нескольких размеров и увидь, как точка прохода разбросана вокруг p_c и как разброс сужается с ростом решётки.

Перколяция — Изображение из программы
Изображение из программы

Что происходит

Открывай узлы (или связи) случайно с вероятностью p и спрашивай, соединено ли что-нибудь левый край решётки с правым. Ниже порога — нет; выше — почти наверняка да, и перемена резкая. Здесь один образец принимается всерьёз: поток растекается от входа по открытому, проход открывается в момент касания выхода, и у каждого образца этот момент наступает при своём p. Предскажи его, подними p, открой узлы руками; затем прогони сотни образцов нескольких размеров. Их точки прохода рассыпаны вокруг p_c = 0,5927 для узлов и 1/2 для связей, и разброс сужается с ростом решётки: p_c — место, где он сошёлся бы для бесконечной решётки.

Уравнения модуля
Уравнения
узел открыт с вероятностью p; открытые соседи объединяются в один кластер
цепочка 1D:  P(соединяет края) = p^L точно
квадратная решётка 2D, узлы:  p_c = 0.592746 (измерено);  связи:  p_c = 1/2 ТОЧНО - самодвойственность
двойственность:  двойственная решётка пересекается ровно тогда, когда исходная нет, поэтому прямоугольник (L+1) x L из узлов пересекается при p = 1/2 с вероятностью 1/2 для любого L
кубическая решётка 3D, узлы:  p_c = 0.3116
гигантский кластер:  ниже p_c наибольший кластер локален; выше - конечная доля всей сетки

Другие эксперименты

К каталогу
Теория графов — Изображение из программы

Math

Теория графов

Кратчайшие пути, остовные деревья и потоки на одном графе, нарисованные по мере счёта: рябь Дейкстры, острова Краскала, пути Эдмондса–Карпа и разрез, равный потоку.

Вороной и Делоне — Изображение из программы

Math

Вороной и Делоне

Клетки ближайшего соседа, которые перестраиваются, пока тянешь их точки; двойственная им триангуляция Делоне с пустыми кругами; диски, растущие в клетки; и релаксация Ллойда, превращающая их в шестиугольники.

Задача коммивояжёра — Изображение из программы

Math

Задача коммивояжёра

Маршрут, который укорачивается у тебя на глазах — жадный, 2-opt, распутывающий рёбра по одному, отжиг, перелезающий через стену, — против точного оптимума для тринадцати городов и перебора всех маршрутов для восьми.