August 1, 2001

Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(1st) pages 344-355 (Section 9.1.1 and 9.2.1)

(2nd) pages 544-550 (Section 12.2.1 and 12.2.1)

Additional material

A simple cycle is a path

of which the first and last vertex are the same,
all other vertices are different, and
which has at least three different vertices.

A cycle is a path

of which the first and last vertex are the same and
which contains a simple cycle.

Vertex
Edge
SimpleGraph

Proof of Proposition 9.11/Proposition 12.11: PostScript and PDF

Implementation of a simple graph by means of an edge list: PostScript and PDF

In order to be able to remove an edge from the set of edges in O(1), we implement the set of edges by means of a List implemented by means of a doubly linked list.

    List edges = new DLList();

The interface Edge is implemented by the class

    public class ELEdge implements Edge
    {
        private Object element;     // element stored in this edge
        private boolean isDirected; // this edge is directed?
        private Vertex origin;      // origin of this edge if it is directed, otherwise one of the end vertices
        private Vertex destination; // destination of this edge if it is directed, otherwise the other end vertex
        private Position position   // position of the List in which this edge is stored

        ....
    }

A directed edge from vertex origin to vertex destination with element element can be added to edges as follows.

    Edge edge = new ELEdge(element, true, origin, destination, null);
    Position position = edges.insertFirst(edge);
    edge.setPosition(position);

The edge edge can now be removed from edges as follows.

    edges.remove(edge.getPosition);

Question

Draw a smallest (in number of edges) free tree with 5 vertices. Draw a largest (in number of edges) free tree with 5 vertices. Draw a smallest (in number of edges) forest with 5 vertices. Draw a largest (in number of edges) forest with 5 vertices. Is the graph

connected? If your answer is yes, give a spanning tree for the graph. If your answer is no, give a spanning tree for a largest (in number of vertices) connected component of the graph.