Случайное простое поколение связного графа с данной разреженностью

Question

Случайное простое поколение связного графа с данной разреженностью

Я пытаюсь найти, что эффективный алгоритм генерирует простой связный граф с данной разреженностью. Что-то как:

Input:
    N - size of generated graph
    S - sparseness (numer of edges actually; from N-1 to N(N-1)/2)
Output:
    simple connected graph G(v,e) with N vertices and S edges

13

algorithm random graph

задан F0RR 11 January 2010 в 11:37

1 ответ

Другие вопросы по тегам:

algorithm random graph

Похожие вопросы:

score 20 · Accepted Answer

Для каждого узла требуется хотя бы один край.

Начните с одного узла. В каждой итерации создайте новый узел и новый рёбер. Край соединяет новый узел со случайным узлом из предыдущего набора узлов.

После создания всех узлов создайте случайные рёбра до выполнения S. Убедитесь, что двойные рёбра не создаются (для этого можно использовать матрицу зависимостей).

Случайный граф выполняется в O(S).