Задачка о генерации случайного связного графа

halyavin
нашёл багу в условии
патч: для всех связных графов содержащих N вершин и M рёбер вероятность построения должна быть равной.

 

Тогда мне не понятно, как вообще это сделать за полиномиальное время.

 

halyavin
Ну построить его можно за время пропорциональное N^2 или даже N+M, а если найти обратную для (x+c)!/(x!*c!) функцию, то память для хеш таблиц или матриц смежности тоже не нужна будет, сразу можно будет результат выводить.

Новая задачка:
А теперь M у нас может быть от N до N*(N-1) и строим ориентированный случайный связный граф, в котором между любой парой вершин существует путь. Хотя это уже наверно слишком просто будет.

 

Я что-то не вижу ни алгоритма, ни доказательства равномерности распределения. Разберите хотя бы случай M=N-1. Мне очень интересно как вы будете это делать не основываясь на изомофризме из доказательства того, что деревьев на n вершинах ровно n^{n-2}.

 

halyavin
Смотри первую половину кода Stiver'а, там как раз строится случайное дерево, ну а дальше случайно добавляем M-(N-1) рёбер.

 

У Stiver'a распределение не равномерное. Рассмотрим случай N=4. Обозначим вершины a,b,c,d. Имеется 16 деревьев - 4 вида ab+ac+ad и 12 вида ab+bc+cd. Таким образом, вероятность сгенерировать дерево первого вида должна быть 1/4. Рассмотрим же теперь последний шаг его алгоритма. В множестве A у него сгенировано дерево изоморфное ab+bc. Для получения дерева первого типа необходимо и достаточно, чтобы была из множества A выбрана средняя вершина b. Вероятность этого - 1/3. Так что подучите математику, прежде чем задачами кидаться.

 

halyavin
Убедил, математику не знал, не знаю и знать не буду, и даже патчи не помогают.
Впрочем в начальном условии было "случайный связный граф" и "равная вероятность рёбер", твой алгоритм берет только один из всех возможных графов состоящих из N вершин и M рёбер. Хотя согласен, если переставить вершины, то вероятность рёбер будет одинаковой.