Here we have a random graph that is quite dense. Each possible edge of this graph with 1000 vertices is included with probability 0.95.
Theoretical considerations show that the expected number of cliques of size in this graph is . This number dips below 1 around , which suggests that the maximum clique should be of size around 120.
We try the same thing with a very sparse graph. We specify that Maple should run 50 iterations instead of the normal 5.
The same argument as above, now with the formula , suggests that the maximum clique in this graph should be of size about 4.
Finally, we try a regular graph.
By setting the infolevel entry for GreedyClique (or for GraphTheory), we can see what happens for each iteration. We specify different thresholds to see if this has any effect: we run twenty iterations with threshold 0 (pick any suitable vertex) and twenty with threshold 1 (pick only vertices with the maximal degree).
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 3 with parameter 0
| |
GreedyClique: step 2: clique grown to size 4
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 6
| |
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 4
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 4
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 6
| |
GreedyClique: step 1: found clique of size 6 with parameter 0
| |
GreedyClique: step 2: clique grown to size 6
| |
GreedyClique: step 1: found clique of size 4 with parameter 0
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 1
| |
GreedyClique: step 2: clique grown to size 4
| |
GreedyClique: step 1: found clique of size 4 with parameter 1
| |
GreedyClique: step 2: clique grown to size 4
| |
GreedyClique: step 1: found clique of size 5 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 3 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 6 with parameter 1
| |
GreedyClique: step 2: clique grown to size 6
| |
GreedyClique: step 1: found clique of size 4 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 1
| |
GreedyClique: step 2: clique grown to size 4
| |
GreedyClique: step 1: found clique of size 3 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 6 with parameter 1
| |
GreedyClique: step 2: clique grown to size 6
| |
GreedyClique: step 1: found clique of size 4 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 4 with parameter 1
| |
GreedyClique: step 2: clique grown to size 4
| |
GreedyClique: step 1: found clique of size 4 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 3 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
GreedyClique: step 1: found clique of size 5 with parameter 1
| |
GreedyClique: step 2: clique grown to size 5
| |
We can also find an independent set in the same graph.
GreedyClique: step 1: found clique of size 9 with parameter 0
| |
GreedyClique: step 2: clique grown to size 11
| |
GreedyClique: step 1: found clique of size 10 with parameter 1/7
| |
GreedyClique: step 2: clique grown to size 10
| |
GreedyClique: step 1: found clique of size 9 with parameter 2/7
| |
GreedyClique: step 2: clique grown to size 11
| |
GreedyClique: step 1: found clique of size 9 with parameter 3/7
| |
GreedyClique: step 2: clique grown to size 12
| |
GreedyClique: step 1: found clique of size 11 with parameter 4/7
| |
GreedyClique: step 2: clique grown to size 12
| |
GreedyClique: step 1: found clique of size 11 with parameter 5/7
| |
GreedyClique: step 2: clique grown to size 11
| |
GreedyClique: step 1: found clique of size 9 with parameter 6/7
| |
GreedyClique: step 2: clique grown to size 10
| |
GreedyClique: step 1: found clique of size 11 with parameter 1
| |
GreedyClique: step 2: clique grown to size 11
| |
We show the resulting clique and independent set.