How to find all simple graphs of order n? | Sololearn: Learn to code for FREE!
New course! Every coder should learn Generative AI!
Try a free lesson
0

How to find all simple graphs of order n?

Hello all this is my first post, I am trying to write a program in python that will generate every single adjacency matrix(from graph theory) with a specific number of vertices and then test that adjacency matrix for various conditions. I have already figured out a way to this using many for loops but it's way too slow. I am only interested in graphs that are: connected, of order n, and simple. But I do need to be sure that my program has checked all graphs of that order. The example output for a graph of order 2 would be: just one graph- two vertices connected by a single edge or in list form [[0,1],[1,0]].

13th Jun 2018, 3:35 AM
Alex Brassington
Alex Brassington - avatar
1 Answer
+ 1
I think that what you want is a bit too much. The number of n-vertices simple connected graphs grows extremely quickly with n. See : http://oeis.org/A001187 For n=8, you would have to find more than 250 millions of them and for n=9 it exceeds 66 billions of them !! It's pretty normal that your loops are slow... but there is no good way to consider ALL simple connected graphs of order n. Maybe you should consider another way for solving your problem.
21st Jun 2018, 4:57 PM
Stéphane Dumas
Stéphane Dumas - avatar