An edge connects two vertices in a graph. It is represented by an ordered pair: the first endpoint is the source, and the second is the destination. Thus, (v1, v2) permits movement from v1 to v2; the reverse direction requires a separate edge. section 14.1
Choose the edge form that matches the graph’s constraints:
- A directed edge has a source and destination, so it can model one-way movement. section 14.1 section 14.3.1
- A loop connects a vertex to itself; simple graphs usually exclude loops and multiple edges between the same vertices. section 14.1
- A multigraph permits multiple edges between two distinct vertices, while a weighted edge adds a value such as distance or cost. section 14.1
Modeling a delivery map
Place a vertex at each road intersection and add an edge for every permitted street direction. A two-way street becomes two opposite edges; one-way streets create only one direction. Counting or weighting these edges then supports route calculations. section 14.3.1
G = ([v1, v2, v3, v4], [(v1,v2),(v1,v3),(v2,v4)])
Inspect a compact graph representation in which vertices are listed separately from ordered-pair edges. section 14.1
