Ol?
I am looking for an algorithm that gives me groups of knots in a net-structure.
Every knot is connected to others ... etc ...
But I want the groups in a way, that the knots in a group have no direct connection to each other!
In the end every knot sould be in one group and the number of groups should be minimal.
Where can i find Informations about that?
No, I thing that is not what I mean.
A clique are Knots which have conections to each other.
But I want to split a network into groups of knots which have no connection to each other ...
A - B
| |
C-D
in that case A, D are independent and C, B.
In more complex constructions it's not so easy. (And the number of groups should be minimal!)
I apologize for being so terse in my previous reply; you *are* indeed looking for cliques. Allow me to
explain. For any graph, a graph complement exists. It can be constructed as follows --
1) for any pair of vertices v_i v_j, ad an edge e_ij if it not already exists;
2) remove all edges v_kl from the graph that were originally present.
A graph plus its complement yield a 'complete graph'. If two vertices v_i and v_j didn't have an
edge e_ij, the complement of the graph will contain this edge. A group of vertices *not* directly
reachable in the original graph make up a clique in the graph complement.
Finding those cliques, or '(maximal) complete sub-graphs' is an NP-complete problem though.
Suppose n cliques exist C_1, C_2 ... C_n. Remove any clique C_i that is a subset of the union
of one or more other cliques. Repeat this step until no clique can be remove anymore. The
cliquest represent the disjoint groups you're looking for.
kind regards,
Jos