Shortest paths, colouring, and planarity
Graph algorithms find the quickest routes, schedule exams without clashes, and decide whether circuits can be laid out without crossings.
Weighted graphs
In a weighted graph, each edge has a cost: distance, time, or price. Road maps are weighted graphs, and the main question is often the cheapest path between two vertices.
Dijkstra's algorithm
Dijkstra's algorithm finds shortest paths from a source in graphs with non-negative weights. It repeatedly selects the unvisited vertex with the smallest known distance, marks it final, and updates its neighbours' distances. Navigation apps use refined versions of it. With a priority queue it runs in about \(O(E\log V)\) time.
Breadth-first search
For unweighted graphs, breadth-first search (BFS) explores vertices layer by layer from the source and finds shortest paths in terms of edge count. It underlies 'degrees of separation' calculations in social networks. Depth-first search (DFS) instead goes as deep as possible first and is useful for detecting cycles and connectivity.
Graph colouring
Colour vertices so that adjacent vertices differ. The chromatic number \(\chi(G)\) is the fewest colours needed. Scheduling exams so no student has two at once is colouring a graph of courses, with an edge for each shared student; colours are time slots. Bipartite graphs need only 2 colours, and \(K_n\) needs \(n\).
The four colour theorem
Any map can be coloured with four colours so that neighbouring regions differ. Proved in 1976 with extensive computer checking, it was the first major theorem proved with essential computer assistance, prompting debates about what counts as a proof.
Planar graphs
A graph is planar if it can be drawn without edges crossing. For connected planar graphs, Euler's formula holds: \(V - E + F = 2\), where \(F\) counts faces including the outer one. \(K_5\) and \(K_{3,3}\) are not planar, which is why three houses cannot each be connected to three utilities without pipes crossing.
V - E + F = 2Worked example
A cube's skeleton has 8 vertices and 12 edges and is planar. Euler's formula gives \(F = 2 - 8 + 12 = 6\) faces, matching the cube's 6 square faces. Euler's formula works for any convex polyhedron.
Common mistakes
Using Dijkstra's algorithm with negative edge weights, where it can fail. Confusing BFS and DFS. Forgetting the outer face in Euler's formula. Assuming a graph is non-planar just because one drawing has crossings.
Key takeaways
Dijkstra's algorithm finds shortest paths with non-negative weights; BFS does so for unweighted graphs. Graph colouring models scheduling, and the chromatic number is the minimum colours needed. Planar graphs satisfy \(V - E + F = 2\); \(K_5\) and \(K_{3,3}\) are not planar.
Flashcard
Edges carry costs
Check your understanding
A connected planar graph has 10 vertices and 15 edges. How many faces does it have?