>
|
|
>
|
|
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.
>
|
|
| (1) |
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.
>
|
|
>
|
|
| (4) |
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.
>
|
|
| (7) |
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).
>
|
|
| (8) |
>
|
|
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
| |
| (9) |
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
| |
| (10) |
We show the resulting clique and independent set.
>
|
|
>
|
|
>
|
|