Песочная модель. Лекция 1

YouTube

Песочная модель представляет собой связный граф, в вершинах которого лежат песчинки. Как только число песчинок в вершине v становится больше или равно числу рёбер, выходящих из v, эта вершина отдаёт каждой из соседних вершин по одной песчинке, такая операция называется обвалом. Хотя бы одна вершина в графе объявляется стоком: там мы обвалов не делаем, можно считать, что все песчинки, туда попадающие, исчезают из системы. Несложно показать, что из любой начальной конфигурации песчинок в вершинах операциями обвалов можно прийти к стабильной конфигурации — где обвалов сделать более нельзя — и что эта финальная конфигурация определена однозначно.

Песочная модель была придумана несколько раз в разных контекстах и таит множество открытых вопросов с красивыми картинками.