Пописываю вот курсовую
Надо генерировать граф для тестирования алгоритмов поиска мин дерева остова
Так вот вопрос:
Никто не встречал алгоритма генерации графа с заданной степенью вершины?
реализовал 2 варианта(оба простейшие)
1 — ый — рёбра добавляются к следующим ближайшим соседям
БЫСТРО, но вот структура получается очень похожая, однотипная, — не подходит для проведения экспериментов
2 — ой — в общем нормальный рандом, только вот очень ДОЛГО получается(минут 5 ждешь, пока сгенерит граф со 10000 вершин и степенью = 10)
нутром чую, что есть хоть какое-то подобие алгоритма, тока вот ни придумать путёвого ни найти не могу

Можно рассмотреть задачу в более общем виде: построение графа с заданной степенной послодовательностью. Решается она с помощью алгоритма, называемого иногда L-процедурой. Так вот в этой L-процедуре на каждом шаге есть определенная свобода выбора, поэтому выбор можно делать случайный.

Как работает L-процедура. Построим пустой граф из n вершин, рядом с каждой вершиной v напишем число d(v) -- требуемую степень. Выберем произвольную вершину v с d(v) > 0 (если таковых нет, то работа завершена). Рассмотрим множество A, состоящее из d(v) вершин, отличных от v и имеющих наибольшие значения d. Соединим v с вершинами из A;
скорректируем требуемые степени (уменьшим d(v) и d(x), x \in A) на единицу. Перейдем к следующему шагу.

Известно, что если реализация последовательности вообще существует, то L-процедура ее найдет (при любом выборе вершин v) -- это т.н. теорема Гавела-Хакими. Реализация алгоритма будет достаточно быстрой, если использовать для выбора A приоритетную очередь. Тогда получается сложность O(E \log V).