Exercises for Chapter 2 of Hage and Harary book

1. Refer back to Exercise 1 for Chapter 1, which relates to the figure on page 4 of Hage and Harary.
   1. How many edges would there be in a "complete" graph with four nodes?  (Your answer should be either a number, or an explanation of what additional information would be needed to determine the number.)
   2. Is that graph complete?  Explain.
   3. Is that graph "connected"? Explain.
   4. With four nodes, what is the minimum number of edges required to make the graph connected?  
   5. If the graph is NOT connected, skip to the next item.  If it IS connected, could you remove any of the edges, and still leave the remaining graph connected?  (Specify which edges.)
   6. If the graph IS connected, skip this item.  If it is NOT connected, how many components does it have?
2. In Figure 1.9, page 13, identify each node that is a "cutnode". Briefly explain why a person occupying a cutnode position in a social network may be able to exert more influence than persons occupying other node positions.
3. In Figure 1.9, page 13, identify each edge that is a "bridge".  Briefly explain why people who occupy nodes in a social network might attach greater importance to a bridge than to other edges.
4. Construct an adjacency matrix for the graph in Figure 1.9, page 13, following the book's convention that a node is NOT adjacent to itself.    Count the number of edges in the Figure.  Count the number of occurrences of the number "1" in the matrix.  What should be the relationship between the two?
5. If an adjacency matrix A represents friends, its square will represent friends of friends, its cube friends of friends of friends, etc. Raising a matrix this large to higher powers is a tedious task for which computers are better suited than humans. There is, however, one difficulty in analyzing this particular matrix in Mathcad. The adjacency matrix for 11 nodes has 11x11=121 elements, and Mathcad's simple way of entering a matrix only works for those with 100 or fewer elements. Here are two options, the first of which is more straightforward, the second of which will teach you more about Mathcad operations for large matrices. You may choose either option:
   • Remove node "g" and the "gf" edge that touches it. Delete the g row and the g column from the 11x11 adjacency matrix, and proceed to analyze the resulting 10x10 matrix. Or:
   • Enter the 11x11 matrix in two pieces, each smaller than 100 elements; combine the two pieces using the "stack" operation; and then proceed to analyze the full 11x11 matrix. (Note: In addition to "stack", for combining two matrices one atop the other, Mathcad also has the "augment" function for combining two matrices, one beside the other.) Details: The first 9 rows have 99, which is fewer than 100 elements, so they could be given a name, say A, and entered the usual way, by typing A: and in the Insert Matrix dialog box choosing 9 rows and 11 columns, and filling in the values. The last two rows, with 22 elements, could be entered as a second matrix, say B, with 2 rows and 11 columns. Then the matrices A and B could be combined into the desired matrix, say C, by typing C:stack(A,B) and the result checked by typing C= to display it.
6. Using Mathcad, calculate the square, cube, 4th, and 5th powers of the matrix in problem 5.  
7. Give a verbal interpretation of the entry in row a, column f, of the 5th power of the matrix.