CS410, Summer 1998
Quiz #12
July 31

Consult no sources.				Name:

1. What is a graph (in the sense of this class, of course)?  Be sure
to briefly define any subterms used in the definition.

2. What is a cycle in a graph?

3. What is a dag?

4. What is the asymptotic space requirement of the adjacency list
representation of a graph?

5. What is the asymptotic space requirement of the adjacency matrix
representation of a graph?

ANSWERS
=======

2 points each

1. A graph is a set of vertices and a set of edges.  Vertices are objects.
   Edges are pairs of vertices.

2. A cycle is a path with a repeated vertex.

3. A dag is a directed acyclic graph.

4. O(n+m) where n is the number of vertices and m is the number of edges.

5. O(n^2) where n is the number of vertices.