Hi all,
Is there some easy way to find out all connected undirected multigraphs up to E edges?
For instance:
1 edge
a-b
2 edges:
a-b-c
a-b, a-b
x edges: ?
Regards,
Callegaro
Your question is unclear. Given 3 nodes, there should be a 3 edges for a completely connected undirected graph.
Hi Richard,
I don't want to construct only complete graphs (eg: K2, K3, K4...), but yes, they should be part of my solution.
I'm fixing the number of edges, not the number of nodes.
So, for one edge, I can only build one graph which links node A and node B.
For two edges, two graphs:
- Node A links node B, node B links C.
- Two parallel edges between nodes A and B.
And so on.
PS: Self-loops are not allowed.
Thanks for your attention
So, self loops are not allowed, but parallel edges are allowed. That means that for every (n+1) solution must be a superset of the solution for n edges. I say start with the basic solution of two nodes with all edges connected between them, and disconnect them one at a time to a new node until you are reduced to the last edge. Then iterate for every pair of nodes.
But in this way we will fix again the node set.
If I want to discover all possible graphs with 10 edges, I'll need to iterate from 2 to 11 nodes, since in the worst case a complete graph with 10 edges will have 11 nodes.
A K11 (complete graph with 11 nodes) will have 55 edges. And I think that a naive algorithm will be impractical in this case. For small problems, OK. But I want to reach at least 12 edges.
Thanks again
You can construct all such graphs by the following recursive procedure:
Suppose that you have a total of E edges, and at some stage you constructed a connected multigraph G using exactly e of these edges.
Add the new (e+1)-th edge recursively to this graph by either
a) fusing only one of it's ends to any of G's vertices (and the other end is left free), or
b) fuse both of it's ends to any two distinct vertices of G
(in both cases you fuse it in such a way to avoid making a loop with this new edge).
- Badges
- Science topic
- Similar topics
- Computer Science