Contract

State whether vertices have fixed indices or external labels, whether edges are directed, and whether weights or duplicate edges are allowed. Define error results for invalid vertices and how a missing edge is represented.

Implementation choices

A fixed matrix provides direct adjacency tests and simple bounds checks for a small graph. Adjacency lists store only present edges and suit sparse neighbour traversal. Removing a vertex requires updating incident edges and any index mapping; it is not just deleting one display label.

Applications

1. Transport networks model connections and routes.
2. Social networks model relations between accounts or people.
3. Task-dependency graphs describe prerequisite relationships.
4. Communication graphs model devices and links.
5. Web link graphs model directed connections between pages.

Model carefully

An edge should represent a well-defined relation. Friendship may be undirected while following an account may be directed. Travel distance and fare are different weights. A DFS or BFS traversal answers reachability questions, but a particular application may require additional algorithmic steps.

Complexity

The ADT alone does not promise every operation is constant time. In a matrix, a valid edge lookup is O(1); a whole neighbour row scan is O(V). Lists have degree-based scans and O(V + E) storage. Separate the logical contract from the chosen performance characteristics.