5.1Introduction to Graph Theory
5.1.1 Introduction
The subject of graph theory and networks is an area of topology that is rapidly moving into mainstream mathematics. It has modern applications in artificial intelligence, data mining, large‐scale communication networks, and industrial scheduling. Few subjects in mathematics can be traced back to such an exact and interesting beginnings as graph theory to the famous Seven Bridges of Konigsberg Problem, solved by the Swiss mathematician Leonhard Euler in 1736.
The town of Konigsberg, Prussia (now Kaliningrad, Russia), rests on the banks of the Pregel River, and as it flows through the town, it divides the town into four distinct regions connected by seven bridges, illustrated in the accompanying drawing. The town flourished in the seventeenth and eighteenth centuries, and the story goes that the people of Konigsberg spent their evenings strolling throughout the city, crossing the seven bridges that spanned the river. The question was asked whether it was possible to start at one of the four land areas, cross each bridge exactly once, and return to the starting point. The mathematician Euler learned of the problem and in a published paper1 demonstrated that in
order for a person to cross each ...
Get Advanced Mathematics now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
