CMPE 220

HW #4

 

DUE: 28.11.2002 Thursday at 13:00 (ETA Z05)

 

1.     a-) Draw the following graphs:

                                                             i.      K7

                                                           ii.      K4,4

                                                        iii.      C7

                                                         iv.      W7

                                                           v.      Q4

b-) Find adjacency matrices for the graphs given in part “a”.

 

2.     How much storage is needed (in terms of bytes) to represent a simple graph with v vertices and e edges using

 

                                                             i.      adjacency lists?

                                                           ii.      an adjacency matrix?

                                                        iii.      an incidence matrix?

 

(Assume that 1 bit is used for Boolean values, 4 bytes are used for integer values (i.e. Current 32 bit architectures) and v < 232 and e < 232 )