- The definition of a `clique' is a complete subgraph. wikipedia entry on Clique problem. You may recall that in class there was frequent mention of complete subgraphs corresponding to clusters of cities with related names, but, alas, I had forgotten that such subgraphs were called cliques. The clique decision problem (does a given graph contain a clique of a given size) was one example of a an important NP-complete clique problem.
- The clique cover problem is another important NP-complete clique problem which is pretty much exactly our similar city name cluster problem ( wikipedia entry for Clique cover problem). The graph k-colorability problem on the on the complement graph ( wikipedia entry for complement graph) is another way of viewing the Clique cover problem (so, the algorithm work for the Clique cover problem is just the algorithm work for the colorability problem, which is the approach the friends.c program takes as well).
- Looking at the code for the colors method in friends.c,
we can see that it is exploring a tree in a depth first manner.
The root of the tree corresponds to node 1 being given color 1.
A step down the tree is done by calling colors with the next
position (p+1) with the color i. This call is in a for loop that
runs i from 1 to maxcolor-1 that are also less than or equal to P+1
(you can see this for loop as walking the siblings of the tree whose
root is p). We only continue the exploration of a branch of the tree
if `possible' is true. This is looking at all the vertices that
came earlier and making sure that if they are connected to p+1,
then they don't have the color i (if they are connected and have
the color i, then possible=0 is executed setting the flag that
prevents the recursive call from happening).
When p == n (i.e., we have hit the last city), then the tree has been expanded to maximum depth down this branch. We then go through the color assignments and set mc to the maximum color value used. If this value is less than maxcolor, then we have found a `better' answer and maxcolor is updated. You can think of the index p as a pointer to the top of a stack of colors (kept in the array col) that mirrors the depth first traversal of the space of possible color assignments.

- In main, when the matrix a[i][j] is initialized, all entries are initiallized to 1. Then, when a city name is fgets'd in, if close is true between it and an earlier city name, then that part of the matrix is set to 0 (making the matrix the matrix for the complement graph upon which colors then gets invoked).
- Note: colors is a brute-force exponential time algorithm that pretty much exhaustively tries all the possible answers. However, it runs fast for the contest because the maximum graph size is 10 vertices.