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?