Introduction and History of Basic Graph Algorithms

History of graphs

A graph is a collection of pairs—pairs of integers, pairs of people, pairs of cities, pairs of stars, pairs of countries, pairs of scientific papers, pairs of web pages, pairs of game positions, pairs of recursive subproblems, and even pairs of graphs. Mirroring is the most common method for visualizing graphs; the underlying objects being paired are usually called vertices or nodes, and the pairs themselves are called edges or arcs, but in fact, the objects and pairs can be anything at all.

Among the earliest examples of graphs are road networks and maps thereof. Roman engineers constructed a network of more than 400 000 km of public roads across Europe, western and central Asia, and northern Africa during the height of the Roman empire. Travelers on the road network would carry itineraries, which were either simple lists or more pictorial representations of the landmarks and distances along various roads. The Tabula Peutingeriana, a 13th-century scroll depicting the entire Roman cursus publicus, is widely believed to be a medieval copy of a 5th-century revision of a 1st-century itinerarium pictum ...