CS 163, Spring 2012, Homework 7, due Thursday, May 31

1. Draw a graph that has exactly one maximum clique and exactly one clique that is maximal but not maximum.

2. Suppose we are applying the pivoting version of the Bron-Kerbosch algorithm to the graph shown below.

   1. Which vertex would be picked as the pivot in the topmost recursive call to the algorithm?
   2. What recursive calls to the algorithm would be made directly from this topmost call? List the arguments to each of these recursive calls.

   

3. Suppose we are using the same graph shown above as a seed graph for the Barabasi-Albert model. What is the probability that the first edge added by the model connects a new vertex to vertex a?

4. What is the clustering coefficient of the graph shown above?