Networks: Graphs, Paths and Minimum Spanning Trees
What you must understand
Network questions use graphs made of vertices (nodes) and edges (arcs). You need the language of networks: degree of a vertex, paths, walks, circuits, connected and disconnected graphs, bridges, loops and weighted edges. You should be able to determine whether a graph has an Eulerian trail or circuit using vertex degrees, find shortest paths between vertices, and construct a minimum spanning tree using Kruskal's algorithm (choose the smallest edges that do not create a cycle) or Prim's algorithm (grow a tree from one vertex). You should also interpret network diagrams in real contexts such as transport, scheduling and project planning.
Traps to watch
- Degree counting: a loop contributes 2 to the degree of its vertex.
- Eulerian conditions: an Eulerian circuit requires every vertex to have even degree; an Eulerian trail requires exactly two vertices of odd degree, and the trail must start and end at those vertices.
- Spanning tree size: a spanning tree on n vertices has exactly n − 1 edges; if your tree has more, it contains a cycle.
- Kruskal's algorithm: never add an edge that closes a cycle, even if it is very small.
- Shortest path versus minimum spanning tree: these answer different questions; a shortest path connects two specified vertices, while a spanning tree connects all vertices.
Worked example
A connected graph has 6 vertices and edge weights 2, 3, 3, 4, 5, 6, 7. A minimum spanning tree needs 5 edges. Choosing 2, 3, 3, 4 and 5 (avoiding any cycle) gives a minimum total weight of 17.
Rule of thumb
For Eulerian questions, count odd-degree vertices first: zero means a circuit exists, two means a trail exists, and any other number means neither.