Починим сразу и то, и другое — добавлением фальшивых рёбер. Пусть мы знаем, что у нас всегда меньше D рёбер. Тогда можно сделать так: кинуть кубик с D гранями — если выпало число от 1 до d, где d степень текущей вершины, то перейти по соответствующему ребру, а если больше, то остаться на месте.
Опять-таки, игрушечный пример — 100-мерный куб {0,1}^100. Его вершины — все возможные 2^100 последовательностей 0 и 1, и это совершенно "наш" случай, что все перечислить нельзя.
Конечно, можно просто подкинуть монетку 100 раз (и это как раз пример, аналогичный ацтекскому бриллианту — когда именно для данного графа, из-за его специфики, есть быстрый способ выбрать случайную вершину) — но допустим, что мы это сделать не догадались.
Конечно, можно просто подкинуть монетку 100 раз (и это как раз пример, аналогичный ацтекскому бриллианту — когда именно для данного графа, из-за его специфики, есть быстрый способ выбрать случайную вершину) — но допустим, что мы это сделать не догадались.
Начав в конкретной точке (например, (0,...,0)) — мы на каждом шагу с вероятностью 1/101 переходим по каждому из возможных рёбер, а ещё с вероятностью 1/101 остаёмся на месте. Иными словами, мы либо меняем один из разрядов нашего 100-значного двоичного слова, либо (с небольшой вероятностью) не делаем ничего.
После того, как мы сделаем такое где-нибудь 10000 раз, каждый разряд мы поменяли в среднем около сотни раз. И "ежу понятно" (хотя, конечно, надо доказывать!), что на такой куче "перещёлкиваний" мы получили уже почти-совсем-случайное распределение.
После того, как мы сделаем такое где-нибудь 10000 раз, каждый разряд мы поменяли в среднем около сотни раз. И "ежу понятно" (хотя, конечно, надо доказывать!), что на такой куче "перещёлкиваний" мы получили уже почти-совсем-случайное распределение.
Казалось бы, отсюда можно получить уже готовый рецепт генерации (почти) случайного разбиения ацтекского бриллианта. А именно: мы знаем, что граф с вершинами-разбиениями связен относительно перестроек квадратиков. Берём какое-нибудь фиксированное начальное разбиение, например, просто все доминошки ставим вертикально. И на каждом шаге выбираем случайный квадрат 2x2. Если его можно перестроить — перестраиваем. Если нельзя — не трогаем. Как раз получается добавление фальшивых рёбер (ибо теперь у нас из каждой вершины исходит одно и то же их количество — просто многие ведут в неё же).
Вот пример такой симуляции (за эти картинки спасибо И. Батманову и К. Люборту):
(кстати, видно, что один из квадратиков "развернулся обратно")
40-я — пары горизонтальных доминошек посередине уже порождают вертикальные другой чётности