Предположим, что число вершин в графе задано как n. (мы можем установить это с помощью пользовательских входов и т. д.)График с n вершинами - как печатать все возможные комбинации графов
Я хотел бы напечатать все возможные случаи соединения вершин с помощью ребер. (Итак, я хотел бы напечатать все возможные (простые) связанные графы n вершин.)
Кроме того, для каждого случая я хотел бы напечатать степень каждой вершины в каждом случае.
Наивным, но простым решением было бы создание всех возможных графиков и фильтрация не связанных между собой.
Создайте набор всех возможных ребер. Есть n(n-1)/2 из них, и это будет размер набора.
Найти power set необходимого набора. Этот набор мощности представляет собой все возможные графики, которые могут быть созданы.
В статье в Википедии также дается algorithm для расчета набора мощности набора. This post также обсуждает этот вопрос (java)
Для каждого подмножества, созданного - проверьте, подключено оно или нет. это можно сделать с помощью алгоритма обнаружения, такого как BFS. График связан тогда и только тогда, когда BFS обнаружил все вершины, начиная с одного (случайного) источника.
Действительно ли имеет порядок вершин? Циклы 1 -> 2 -> 3 -> 1 и 1 -> 3 -> 2 -> 1 считаются двумя разными графами? –
@OpDeCirkel, AFAIU [простой график] (http://en.wikipedia.org/wiki/Graph_ (математика) #Simple_graph) –
К сожалению. Мой пример неправильный. Но опять же графики (1-2,2-3) и (1-3,2-3) в качестве двух разных графиков? –