# 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:

- Supplementary Exercises, Page 433, Problem 10.
- 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.
- 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.)
- 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.
- (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?