Dear all,
I'm new to Mathematica and would love to use the language to solve a network problem, which bothers me for a while. I'm trying to find the minimal amount of cliques that I need to cover the whole network using each node only once. During my Internet search I discovered this site https://mathematica.stackexchange.com/questions/26296/is-there-a-function-to-generate-a-minimal-clique-cover ,which already tries this. But the posted program returns not the number I'm looking for.
This is as far as I got at the moment:
g = Graph[{0 <-> 1, 0 <-> 4, 0 <-> 7, 0 <-> 10, 0 <-> 14, 1 <-> 3,
1 <-> 4, 1 <-> 6, 1 <-> 7, 1 <-> 11, 1 <-> 13, 1 <-> 16, 2 <-> 5,
2 <-> 7, 2 <-> 8, 2 <-> 14, 2 <-> 15, 2 <-> 16,
3 <-> 4, 3 <-> 6, 3 <-> 12, 3 <-> 13, 3 <-> 16, 3 <-> 17, 4 <-> 5,
4 <-> 6, 4 <-> 8, 4 <-> 16, 5 <-> 7, 5 <-> 8, 5 <-> 12, 5 <-> 13,
5 <-> 16, 5 <-> 18, 5 <-> 19, 6 <-> 14, 7 <-> 14, 7 <-> 15,
7 <-> 18, 7 <-> 19, 8 <-> 9, 8 <-> 11, 8 <-> 15, 8 <-> 16,
9 <-> 12, 9 <-> 13, 9 <-> 14,
10 <-> 15, 10 <-> 19, 11 <-> 16, 11 <-> 17, 11 <-> 18, 12 <-> 19,
13 <-> 17, 13 <-> 18, 13 <-> 19, 15 <-> 16, 15 <-> 17, 15 <-> 19},
VertexLabels -> "Name"]
a = FindClique[g, Infinity, All]
Note: I know that I have to improve the implementation of my graph, but this I'll do on my own later on.
With FindClique[,Infinity, All] I've got every single Clique which is possible besides the 'trivial Cliques' containing only the edge itself, which I would like to allow additionally.
My idea, which I failed to implement, is the following one:
First I could create a new graph, with the edges representing the former found cliques, and connect them only if the cliques they represent contain one or more equal edges. Afterwards I could take the minimum of independent edges of this new graph and check if they contain as many edges as I had in the first graph(in this example 20). If that's the case I'm done and have my number, else I could take another minimal sample or increase the number by 1 until I found my number.
Do you think this is an appropriate way of solving my issue and do you have any suggestion how to tackle it?
Best, Robert