Researched
Graph Theory (Euler)
Euler's solution of the Königsberg bridge problem (1736) founds the study of networks of points and links.
Open in the interactive tree →Euler proved that no walk crosses each of the seven bridges exactly once, using only the pattern of connections; it counts as the first theorem of graph theory and a seed of topology. Graphs now model roads, the internet, molecules, social networks and search ranking.
Prerequisites
- Geometry (Euclid)~300 BC
Unlocks
- Topology1895
- Complexity Theory & NP1971Many NP problems (travelling salesman, colouring, cliques) are graph problems
- Four Colour Theorem Proved1976
- Web search and PageRank1998The web is a graph of pages and links, ranked by a random walk on it