Зато рёбер из каждой вершины выходит не так много — не больше 2n^2=20.000, что вполне компьютерно-реалистично.

И можно рассмотреть блуждание по такому графу — приходим в вершину, уходим по случайно выбранному ребру, оттуда опять по случайно выбранному ребру, и так далее.

Так вот — если так "побродить" достаточно долго, то получается (почти) равновероятное распределение на том, куда мы в принципе можем прийти. И это и есть один из способов генерации случайного разбиения. Но тут нужно быть аккуратным и в том, как генерировать, и в том, когда останавливаться (а ещё есть красивые слова "coupling from the past", которые позволяют гарантировать, что получаемое разбиение совсем честно случайно).

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

Добрался до Лиона, и теперь могу показать кусочки их математической фрески в лучшем качестве:

Воздушный шар с расслоением Хопфа —

Солнце, универсально накрывающее сферу без трёх точек —

Дикий узел —

Кстати — вот одно из совершенно потрясающих рассуждений в комплексном анализе (увы — для тех, кто его уже немного знает), теорема Пикара. Целая (голоморфная на C) функция, не принимающая хотя бы два значения, константа.
Потому что — универсальная накрывающая над C без двух точек это диск. Непрерывное отображение можно поднять до отображения универсальных накрывающих. А универсальная накрывающая над C без двух точек (=над сферой без трёх) это диск.
И если мы начали с целой функции, бьющей в C без двух точек — то получаем отображение из C в диск, то есть ограниченную целую функцию. А ограниченная целая функция — константа.

Часы в чайной комнате UMPA тоже соответствующие —

Но давайте я продолжу этот рассказ. Итак, пусть у нас есть абы какой связный граф G. Рассмотрим вот такой процесс на нём: мы начинаем из какой-то вершины, и каждый раз переходим в случайно выбранного соседа этой вершины.

Вообще, такие процессы называются _цепями Маркова_. "Такие" — это значит, что есть множество состояний, для каждого состояния задано, с какой вероятностью в какое состояние мы переходим, причём эта вероятность зависит только от того, где мы сейчас, но не от того, где мы были раньше. Ну и — чтобы процесс был задан полностью, нужно ещё задать начальное распределение (где и с какой вероятностью мы начинаем; например, можно начать просто в заданной точке).

"Игрушечный пример" тут — лягушки, прыгающие между сушей и болотом. Допустим, что лягушка на суше понимает, что ей там плохо, и всегда прыгает в болото. А лягушкам в болоте интересно, что там на суше, и каждая из них решает, остаться там или рискнуть выползти на сушу, с вероятностью 1/2.

Посмотрим, как будет делиться популяция лягушек, если в начальный момент они все сидят в болоте:

Невооружённым глазом видно, что распределение лягушек сошлось к соотношению "2/3 в болоте, 1/3 на суше", которое за один шаг переходит в себя. Такое распределение называется _стационарным_.

Оно всегда (ну, пока граф конечный) есть: средние арифметические распределений за первые n шагов всё более и более стационарны, и достаточно взять их предельную точку. И при довольно простых условиях оно единственно и к нему будет сходимость (как мы и видели на примере лягушек выше). А именно, достаточно попросить, чтобы:
- от любого состояния можно было допрыгать до любого (ибо если есть две не связанных экосистемы, то можно комбинировать меру на одной с мерой на другой)
- НОД возможных времён допрыгивания от состояния до себя равнялся бы 1 (если граф состояний двудольный, то лягушки, начавшие в чёрных вершинах, каждый чётный ход и будут в чётных вершинах — и никакого уравновешения).

Слово "стационарный" здесь можно читать просто как аналог слова "инвариантный"/"сохраняющийся операцией", но правильнее так: если взять эту меру в качестве уже начального распределения, то процесс получается инвариантен относительно сдвига по времени. И тут могло бы быть ответвление в сторону космологии, Фридмана, стационарных/нестационарных моделей Вселенной и нетривиальности понимания того, что Вселенная может быть нестационарной, но я, боюсь, всё-таки не готов его писать менее пунктирно и при этом не рисковать соврать более допустимого. :)

Так вот, к чему всё это — к тому, что у нашего "случайного блуждания по графу" тоже есть стационарная мера. Причём мера очень простая и понятная: вероятность вершины пропорциональна степени этой вершины.