Networks and Matrices
Core concepts
Network questions involve vertices, edges, weights, degrees, paths, cycles, and connectivity. You must know Eulerian and Hamiltonian ideas (when a route uses every edge or every vertex exactly once), trees (connected, no cycles, (n-1) edges), and shortest path and minimum spanning tree reasoning. Matrix work includes addition, multiplication, powers, transition matrices for networks, and adjacency matrices representing connections.
Traps to watch
- Degree sums: sum of degrees equals twice the number of edges - use it to check answers.
- Adjacency matrix entries: entry (a_{ij}) counts edges between (i) and (j); (A^2) counts walks of length 2, not paths (walks can repeat vertices).
- Directed vs undirected - arrows matter; a directed edge is one-way.
- Trees: (n) vertices need exactly (n-1) edges and no cycles; extra edges create cycles.
- Matrix multiplication order - (AB\neq BA) generally; check dimensions.
- Transition matrices: columns (or rows) must sum to 1 and the state vector must be a column (or row) consistently.
Worked rule of thumb
For shortest-path problems, list all paths from start to end and sum the weights; eliminate any path that revisits a vertex with positive weights. Example: vertices A–B (3), B–C (4), A–C (10). The path A→B→C has weight 7, less than A→C (10), so the shortest path is A–B–C. Cross-check with degrees: A has degree 2, B has 2, C has 2, and there are 3 edges - sum of degrees 6 = 2×3. ✓