Stochastic Processes: An Introduction
Peter W Jones, Peter G. Smith · 2017
This chapter describes the birth of graph theory. In 1736, Leonhard Euler, one of the greatest mathematicians of all time, published a short paper on the bridges of Konigsberg, a city in Eastern Europe. However, in graph theory the term connected refers to a different, though related, concept. The Konigsberg Bridge Problem is not just looking for a circuit, but rather a special type that hits every edge. In honor of Leonhard Euler, these special circuits are named for him. A similar term is used when allowing differing starting and ending location of the tour. Part of Euler&s;s brilliance was not only his ability to quickly solve a puzzle, such as the Konigsberg Bridge Problem, but also the foresight to expand on that puzzle. What makes a graph Eulerian and under what conditions will a city have the proper tour are discussed in this chapter.