CSE 321 Assignment #8
Spring 2001

Due: Wednesday, May 29, 2001 at the beginning of class.

Reading assignment: Read the text, Discrete Mathematics and Its Applications, sections 7.1-7.4. (We will not discuss pseudo-graphs which are non-standard.) We will also briefly discuss material from section 6.5.

The following problems are from the Fourth Edition of the text:

  1. Supplementary Exercises, Page 433, Problem 10.

  2. Section 6.4, Problem 26, (b). Show the matrix B at the end of each time through the loop of the algorithm. Draw the graph of the final transitive closure. Finally, draw the graph of the reflexive-transitive closure of the same relation.

  3. Let M be a 01-matrix and let I be the identity matrix. Prove that for all n >= 0, (I v M)[n] = I v M v M[2] v ... v M[n]. You will need to use the fact that L (M v N)= L M v L N (where I've written matrices next to each other to indicate boolean matrix multiplication since html doesn't do circled dots conveniently.)

  4. Section 7.3, Problems 34,36,38,40,42,44. For each of these problems give the isomorphism if there is one or explain why there can be no such isomorphism.

  5. (Bonus) The complement of undirected graph G is the undirected graph with the same vertex set as G such that two vertices are joined by an edge in the complement of G if an only if they are not joined by an edge in G. Prove that if G is not connected then the complement of G is connected. Is the converse true, why or why not?