Directed graphs and problems solved with graphs
Read directed graphs, count handshakes and games in a league and find the shortest route by turning the problem into a graph.
- Russia: grade 7
Guide
In the Russian programme (Grades 7-8, Probability and Statistics, introduction to graph theory) a graph is a handy model: vertices are people, towns or teams and edges are relations (friendship, roads, matches). If the relation has a direction ("A overtook B") the edge is drawn with an arrow: a directed graph. A vertex then has a number of outgoing and of incoming arrows.
Classic problems: handshakes in a group of n people (everyone with everyone once), matches in a league (every team plays every other). The sum of the degrees is twice the number of edges, so the edges are half the degree sum; for n vertices all joined we get n·(n − 1) : 2.
A common slip is counting every edge twice. Another is mixing up outgoing and incoming arrows. A route problem is solved by counting the edges of the shortest chain.