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 350-355 (Section 9.1 and 9.2.1)

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

Additional material

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

Which of the preconditions in the implementation of a simple graph by means of an edge list cannot be checked in O(1)?