A graph \(G = (V, E)\) consists of:
- \(V\) = a non-empty set of vertices (nodes)
- \(E\) = a set of edges, each connecting a pair of vertices
The most intuitive: vertices drawn as circles/dots, edges as lines (or arrows for directed).
For \(n\) vertices, an \(n \times n\) matrix where \(a_{ij}\) = number of edges from \(i\) to \(j\).
A table listing each edge with its two endpoints and weight.
A weighted graph assigns a numerical weight to each edge. The weight may represent:
- Distance (km)
- Time (minutes)
- Cost (\$)
- Capacity (litres/sec)
Four cities: 1, 2, 3, 4. Connections (undirected):
- 1–2, 1–3, 2–3, 2–4, 3–4
The matrix is symmetric (undirected). Degrees: \(\deg(1)=2\), \(\deg(2)=3\), \(\deg(3)=3\), \(\deg(4)=2\).
| Edge | Weight (km) |
|---|---|
| 1–2 | 5 |
| 1–3 | 8 |
| 2–3 | 6 |
| 2–4 | 7 |
| 3–4 | 4 |
In a directed graph, \(a_{ij} \neq a_{ji}\) in general. A one-way road from A to B gives \(a_{AB} = 1\) but \(a_{BA} = 0\).
REMEMBER: In an undirected adjacency matrix, the matrix is always symmetric about the main diagonal. Use this as a self-check.
EXAM TIP: When reading a network diagram, systematically list all edges before constructing an adjacency matrix or computing degrees. Missing one edge causes cascading errors.
