|
The functions given here are not applicable to digraphs.
A clique of a graph G
is a complete subgraph of G.
A maximal clique
is a clique which is not contained in any other
clique.
A maximum clique is a maximal
clique of largest size.
An independent set of G is
an empty subgraph of G.
A maximal (maximum) independent set
is defined is the same way
as a maximal (maximum) clique.
Note that an independent set of size k in the graph G
is a clique of size k in the complement graph of G.
The clique and independent set functions presented below are implemented
using one of two algorithms, called here BranchAndBound
and Dynamic.
The algorithms BranchAndBound and Dynamic are briefly
described here.
BranchAndBound : The algorithm is an implementation
of the branch and bound algorithm by
Bron and Kerbosch [BK73].
The algorithm is designed to find maximal cliques and it has been
adapted here to also find cliques of specific size
which may not be maximal.
It attempts to build a maximal clique by trying to expend the
current maximal clique.
Some heuristics are built into the algorithm which enable
to prune the search tree.
Dynamic : The algorithm finds a clique of
size exactly k, not necessarily maximal,
in the graph G by using recursion and dynamic programming.
If a clique of size k exists in G, then, for a given
vertex v of G, there is either a clique of size k - 1
in the subgraph induced by the neighbours of v,
or there is a clique of size k in the graph G - v.
This is the recursive step.
The Dynamic algorithm applies a different strategy
(sorting of vertices and
selection of vertices to consider)
according to the order and density of the subgraph
considered at the current level of recursion.
This is achieved by dynamic programming, hence the name.
This algorithm is due to
Wendy Myrvold [WM].
Comment: When comparing both algorithms
in the situation
where the problem is to find a maximum clique
one observes that in general
BranchAndBound does better.
However Dynamic outperforms BranchAndBound when the graphs
under consideration are large (more then 400 vertices) random graphs
with high density (larger than 0.5%).
So far, it can only be said that
the comparative behaviour of both algorithms is highly
dependent on the structure of
the graphs.
Returns true if and only if the graph G has a maximal clique of size k.
If true, returns such a clique as the second argument.
Al: MonStgElt Default: "BranchAndBound"
If m is true, the function is true if and only
if the graph G has a maximal clique of size k.
If m is false, the function is true if and only if the graph G
has a --- not necessarily maximal --- clique of size k.
If the function is true, an appropriate clique is
returned as the second argument.
When m is false, the parameter Al enables the user
to select the algorithm which is to be used.
When m is true, the parameter Al is ignored.
The parameter Al enables the user to select the algorithm
which is to be used:
Al := "BranchAndBound" or Al := "Dynamic".
See the description given at the
beginning of this section.
The default is "BranchAndBound".
Al: MonStgElt Default: "BranchAndBound"
If m is true and f=0, the function is true if and only
if the graph G has a maximal clique of size k.
If m is true and f=1, the function is true if and only
if the graph G has a maximal clique of size larger than
or equal to k.
If m is true and f= - 1, the function is true if and only
if the graph G has a maximal clique of size smaller than
or equal to k.
If m is false, the function is true if and only if the graph G
has a --- not necessarily maximal --- clique of size k.
If the function is true, an appropriate clique is
returned as the second argument.
When m is false, the parameter Al enables the user
to select the algorithm which is to be used.
When m is true the parameter Al is ignored,
and when m is false, the flag f is ignored.
The parameter Al enables the user to select the algorithm
which is to be used:
Al := "BranchAndBound" or Al := "Dynamic".
See the description given at the
beginning of this section.
The default is "BranchAndBound".
Al: MonStgElt Default: "BranchAndBound"
Finds a maximum clique in the graph G.
The clique is returned as a set of vertices.
The parameter Al enables the user to select the algorithm
which is to be used.
For a description of the algorithm used when
Al := "BranchAndBound" see the
beginning of this section.
When Al := "Dynamic", two steps are required.
- Step 1
- Finding a lowerbound on the size of a maximum clique.
This is achieved by using the dsatur colouring
(dsatur stands for saturation degree) due to
Brélaz [Bre79].
The dsatur colouring gives a reasonably good approximation
to the size of a maximum clique, usually with a penalty of 2 to 3.
- Step 2
- Assume that the lowerbound found in Step 1 if l.
Then a maximum clique is found by finding
the largest possible clique of size k≥l using the
Dynamic algorithm.
The default is "BranchAndBound".
Al: MonStgElt Default: "BranchAndBound"
Finds the size of a maximum clique in the graph G.
The parameter Al enables the user to select the algorithm
which is to be used.
For a description of the algorithm used when Al := "BranchAndBound" see the
beginning of this section.
For a description of the algorithm used when Al := "Dynamic" see the function
MaximumClique.
The default is "BranchAndBound".
Limit: RngIntElt Default: 0
Returns all maximal cliques of the graph G
as a sequence of sets of vertices.
If Limit is set to a positive integer,
returns Limit maximal cliques of G.
Limit: RngIntElt Default: 0
Returns all maximal cliques of size k of the graph G
as a sequence of sets of vertices.
If Limit is set to a positive integer,
returns Limit maximal cliques of size k of G.
Limit: RngIntElt Default: 0
Al: MonStgElt Default: "BranchAndBound"
If m is true, returns all maximal cliques of
size k in the graph G.
If m is false, returns all --- not necessarily maximal ---
cliques of size k.
When m is false, the parameter Al enables the user
to select the algorithm which is to be used.
When m is true, the parameter Al is ignored.
The parameter Al enables the user to select the algorithm
which is to be used:
Al := "BranchAndBound" or Al := "Dynamic".
See the description given at the
beginning of this section.
The default is "BranchAndBound".
Except in the case where m is false and Al is "Dynamic", the parameter Limit, if set to a positive integer,
limits the number of cliques returned.
Maximal independent sets or
independent sets of a given size k
in a graph G can be easily
found by finding maximal cliques or cliques
of size k in the complement
of G.
Only two functions which are concerned with
independent sets are provided: one
finds a maximum independent set and the other
returns the independence number of a graph.
Al: MonStgElt Default: "BranchAndBound"
Finds a maximum independent set in the graph G.
The maximum independent set is returned as a set of vertices.
The parameter Al enables the user to select the algorithm
which is to be used:
Al := "BranchAndBound" or Al := "Dynamic".
See the
function MaximumClique.
The default is "BranchAndBound".
Al: MonStgElt Default: "BranchAndBound"
Finds the size of a maximum
independent set in the graph G.
The parameter Al enables the user to select the algorithm
which is to be used:
Al := "BranchAndBound" or Al := "Dynamic".
See the function CliqueNumber.
The default is "BranchAndBound".
We illustrate the use of the clique
functions with the following graph:
> G := Graph< 9 | [ {4,5,6,7,8,9}, {4,5,6,7,8,9}, {4,5,6,7,8,9},
> {1,2,3,7,8,9}, {1,2,3,7,8,9}, {1,2,3,7,8,9},
> {1,2,3,4,5,6}, {1,2,3,4,5,6}, {1,2,3,4,5,6} ]>;
> HasClique(G, 2);
false
> HasClique(G, 2, true);
false
> HasClique(G, 2, false);
true { 1, 4 }
> HasClique(G, 2, true: Al := "Dynamic");
false
> HasClique(G, 2, false: Al := "Dynamic");
true { 1, 9 }
> HasClique(G, 2, true, 1);
true { 1, 4, 7 }
> MaximumClique(G);
{ 1, 4, 7 }
> AC := AllCliques(G);
> #AC;
27
> AC3 := AllCliques(G,3);
> #AC3;
27
> AC eq AC3;
true
> AllCliques(G, 2, true);
[]
> AllCliques(G, 2, false);
[
{ 1, 4 },
{ 1, 5 },
{ 1, 6 },
{ 1, 7 },
{ 1, 8 },
{ 1, 9 },
{ 2, 4 },
{ 2, 5 },
{ 2, 6 },
{ 2, 7 },
{ 2, 8 },
{ 2, 9 },
{ 3, 4 },
{ 3, 5 },
{ 3, 6 },
{ 3, 7 },
{ 3, 8 },
{ 3, 9 },
{ 4, 7 },
{ 4, 8 },
{ 4, 9 },
{ 5, 7 },
{ 5, 8 },
{ 5, 9 },
{ 6, 7 },
{ 6, 8 },
{ 6, 9 }
]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|