Unit 5
Graphs and networks.
Nodes and edges: the bridges of Königsberg, the shortest route through a network, packets, and PageRank.
Before this unit
The unit, lesson by lesson
Lessons
4 lessons · 23 practice questions · about 2 hours
Nodes and edges
From a town to a graph: nodes, edges and degree, why the degrees always add up to twice the edges, and what a new bridge does to the degrees.
Euler paths
Crossing every bridge once: why Königsberg has no such walk, Euler's rule about odd nodes, where a walk must start, and when it comes back to the start.
Routing packets
The internet as a graph of routers: the shortest route, detours when a cable is cut, a cut that splits the network, and packets that spread over several routes and arrive out of order.
Ranking pages
How a search engine knows what matters: the random surfer, PageRank as a share of time on each page, why a link from an important page is worth more, the damping factor, and visits that settle.