Generating all non-isomorphic graphs for a given number of nodes with specified degrees

12 vues (au cours des 30 derniers jours)
I would like to generate the set of all possible, non-isomorphic graphs for a given number of nodes (n) with specified degrees. Such graphs are relatively small, they may have n = 1-8 where the degree of nodes may range from 1-4.
Generated graphs must be allowed to contain loops and multi-edges. Here, multi-edges have a max value of 2, that is any two nodes may be connected to eachother by a maximum of 2 edges, they may also be connected by 1 edge or 0 edges.
E.G. Generate all possible graphs (thay are allowed to contain loops and multi-edges) with 4 nodes (n = 4) where 2 of the nodes have the degree 2 (2-connected) and two of the nodes have the degree 3 (3-connected).
I have worked this out on paper, there should be 11 different graphs.
Is there an efficient way to generate all possible graphs (with restrictions listed above) with n nodes where the degree of each node is specified ?
Thanks!
-Maxwell Day

Réponses (1)

Christine Tobler
Christine Tobler le 24 Nov 2020
I've attached a script that computes the graphs in your example, here's the plot of all graphs it found:
  10 commentaires
Maxwell Day
Maxwell Day le 30 Nov 2020
Thanks @Christine Tobler,
Now it appears the code is generating the Figure for each graph set properly!
I am attempting to run the degList = [2 2 2 2 3 3] with k = 8 and the following error shows up;
Error using nchoosek (line 29)
The second input has to be a non-negative integer.
Error in generateGraphsMultiNestedLoops (line 43)
lastSetsOfRows = nchoosek(firstSet(end)+1:size(ed, 1), e-k);
From your last comment, it sounds like increasing k should only decrease the memory required to a maximum value where k = e/2, where e = # of edges given by "degList", is this true? If so, should k always be set equal to e/2?
Christine Tobler
Christine Tobler le 30 Nov 2020
k must also be less than e, since we are splitting up the number of edges into k edges, and then e-k other edges. The error is because e-k becomes negative.

Connectez-vous pour commenter.

Catégories

En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by