1

Suppose that we set the number of vertices in a graph as n. (we can set this by user inputs etc.)

I'd like to print all possible cases of connecting vertices using edges. (So, I'd like to print all possible (simple) connected graphs of n vertices.)

Also, for each case, I'd like to print degree of each vertex in each case.

amit
  • 175,853
  • 27
  • 231
  • 333
user1441174
  • 47
  • 1
  • 4
  • Does order of vertices matter? Are cycles 1 -> 2 -> 3 -> 1 and 1 -> 3 -> 2 -> 1 counted as two different graphs? – default locale Jun 07 '12 at 05:17
  • @OpDeCirkel, AFAIU [simple graph](http://en.wikipedia.org/wiki/Graph_(mathematics)#Simple_graph) – default locale Jun 07 '12 at 05:20
  • Oops. My example is wrong. But again are graphs (1-2,2-3) and (1-3,2-3) counter as two different graphs? – default locale Jun 07 '12 at 05:33
  • 1
    @defaultlocale yes. even if some graphs turn out to be isomorphic to some graph, they are treated as being separate. – user1441174 Jun 07 '12 at 05:44
  • Is the graph directed? If so - are you looking for connected or strongly connected graphs? These are two different things. – amit Jun 07 '12 at 05:53
  • @amit undirected. and cases of simple connected graph. (Isn't strongly connected graph a directed graph?) – user1441174 Jun 07 '12 at 06:03
  • @user1441174: It is the same for undirected graphs. For directed graphs - a strongly connected graph is also connected, but not the other way around. `V={1,2,3}, E=(1->2,2->3)` the graph is connected, but not strongly connected. – amit Jun 07 '12 at 06:05

1 Answers1

1

A naive but simple solution would be to create all possible graphs, and filtering out the not connected ones.

Create a set of all possible edges. There are n(n-1)/2 of those, and this will be the set's size.

Find the power set of the required set. This power set represents all possible graphs that can be created.

The wikipedia article also gives an algorithm for calculating the power set of a set. This post also discusses this issue (java)

For each subset created - check if it is connected or not. it can be done using a discovery algorithm such as BFS. The graph is connected if and only if BFS discovered all vertices, when starting from a single (random) source.

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333