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)
$$\text{Example: } e(A, B) = 12 \text{ km}$$
Four cities: 1, 2, 3, 4. Connections (undirected):
- 1–2, 1–3, 2–3, 2–4, 3–4
$$A = \begin{array}{c|cccc} & 1 & 2 & 3 & 4 \ \hline 1 & 0 & 1 & 1 & 0 \ 2 & 1 & 0 & 1 & 1 \ 3 & 1 & 1 & 0 & 1 \ 4 & 0 & 1 & 1 & 0 \end{array}$$
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.
