Swipe to navigate through the chapters of this book
Graph theory is a practical branch of mathematics that deals with the arrangements of certain objects known as vertices (or nodes) and the relationships between them. It has been applied to practical problems such as the modelling of computer networks; determining the shortest driving route between two cities; the link structure of a website; the travelling salesman problem; and the four-colour problem.
Please log in to get access to this content
To get access to this content you need the following product:
The 4-colour theorem states that given any map it is possible to colour the regions of the map with no more than four colours such that no two adjacent regions have the same colour. This result was finally proved in the mid-1970s.
Königsberg was founded in the thirteenth century by Teutonic knights and was one of the cities of the Hanseatic League. It was the historical capital of East Prussia (part of Germany), and it was annexed by Russia at the end of the Second World War. The German population either fled the advancing Red army or were expelled by the Russians in 1949. The city is now called Kaliningrad. The famous German philosopher, Immanuel Kant, spent all his life in the city, and is buried there.
These are named after Sir William Rowan Hamilton, a nineteenth century Irish mathematician and astronomer, who is famous for discovering quaternions [ 1].
We use the term “salesman” to stand for “salesman” or “saleswoman”.
Mathematics in Computing. Second Edition, Gerard O’ Regan. Springer. 2012.
Discrete Mathematics. An Introduction for Software Engineers. Mike Piff. Cambridge University Press. 1991.
Discrete Mathematics and its Applications. 7th Edition. Kenneth H. Rosen Mc Graw Hill. 2012.
- Graph Theory
- Springer International Publishing
- Sequence number
- Chapter number
- Chapter 9