Graph Theory is a very useful and fun subject.
Let us start with a historical problem which is called the Konigsberg Bridge Problem. The city of Konigsberg in former Prussia (now called Kaliningrad, Russia) has two islands in the middle of the rivers. The two islands connected to the mainland by seven bridges. Leonhard Euler in 1736 asked this problem: is it possible to walk from his home around the city and cross each of the seven bridges only once and return home? The key problem lies on the word “to cross each bridge only once”.
Euler simplified the problem this way: each mass of land is considered as a node (or called vertex) and each of the bridge into a link (or called edge). The collection of nodes and links together with the properties and operations on the nodes and links is called Graph Theory. Euler also proved using this simple model that nobody can walk to cross each of the seven bridges once to return home. Thus, the Konigsberg Bridge Problem has no solution!
Since that time, the study of this theory has flourished. Now we can find many applications of graph theory. Just a few of them can be mentioned here:
- Road network can be modeled as graph theory with intersection as node and the midblock as link. Using this graph, you can find the shortest path from your home to your school or office.
- When each region in a map is represented as a node, and the connection of the region with its adjacent regions in the same map is indicated as a link, we will have a graph. Graph theory has lead to some results that you only 4 colors to color all regions in a map such that no adjacent region will be colored with the same color.
- Electrical network is a graph with each of the junction and electrical devices as nodes connected by the wire as links.
- Social network where each person is connected socially with their friends or relatives can be visualized as a graph.
- An activity in a project can be modeled a node. The preceding and successive activities are connected to the current activities. This graph of activities leads to optimization of schedules in project management.
Though Graph theory is very interesting, studying more advanced graph theory can become very complicated. For beginners, pictorial introduction to graph theory explained in very gentle English is very fun and motivating to the young people to learn more on graph theory.