ARC Routing

Arc routing problems are among the earliest problems known in the theory of graphs. The source is the Swiss mathematician Leonhard Euler and his famed Königsberg Bridge Problem posed in 1736. It concerns a walk across the seven bridges of Königsberg that lead across the Pregel River; see Figure II.35a. The question Euler asked was whether or not a walk would exist on which each of the bridges is crossed exactly once. When presenting the problem and its solution to the St. Petersburg Academy, Euler did not use the geographical picture of the city, river, and bridges, but a graph-theoretical representation of them which represents bridges as edges, and the ends of the bridges at an island or the banks of the river as nodes. This representation is shown in Figure II.35b.