Overclock.net banner
1 - 1 of 1 Posts

· Registered
Joined
·
871 Posts
Discussion Starter · #1 ·
How can you generate non-isomorphic graph? |V| is 5 to 6 and |E| is 6 to 7.

I know how to generate isomorphic graph, which is much easy.
First, you generate a graph, V = {0, 1, 2, 3, 4} and E = {<0,1>, <1,2>, <2,3>, <3,4>, <4,0>, <1,3>} Just an example.
Then, you generate an array of a permutation of V. V' = {1, 2, 3, 4, 0}.
Then you just go through the edges E.x = V'[E.x] and E.y = V'[E.y]

But for non-isomorphic graph, even if you randomly choose an edge and change it completely, there is still a chance that it is isomorphic. How do I make sure that it is indeed non-isomorphic?

Of course, I can generate all the permutation then check against it. But this seems to be computational intensive.
 
1 - 1 of 1 Posts
This is an older thread, you may not receive a response, and could be reviving an old thread. Please consider creating a new thread.
Top