In mathematics, we usually only think about these node numbers. The numbers are only used to distinguish the nodes. When we apply the idea of a graph to a concrete problem, these numbers corresponds to different kinds of objects. Let me show two examples to give you some idea.
Example 1: Nodes represent authorsAssume we are describing the following authors:
- William Shakespeare
- Lewis Carroll
- Raymond Smullyan
- Martin Gardner
|Figure 5. Graph example 1. Each node is an English author.|
Example 2: Nodes represent train stationsAssume each node represents a train station. The followings are stations in Berlin, Germany.
- Hackescher Markt
|Figure 7. Graph example 2. Each node is a train station.|
You may think it is odd that I said the relation of English authors and the relation of train station are the same in the sense of a graph. I am often surprised that there are so many similar patterns in this world. There are problems that look totally unrelated, but sometimes the same pattern is hidden deep within them. If you can find a pattern in your problem, and if you can connect it to a known pattern, you might be able to solve your problem. Even your problem is very new and nobody has solved it yet, you then have a chance to find a solution. Mathematics is a powerful tool for finding common patterns in this sense. Of course, you might not be able to find a similar pattern, or may find a pattern that you think is similar, but turns out to be a completely different problem.
The most fundamental pattern in mathematics involves something you can count. People, dogs, cities, stars, musical notes, churches... these objects have one common property: you can count them. For mathematics, they are all the same in this sense of being countable. Therefore, when you have learned how to add numbers once, you have no problem adding any number of people, or number of dogs, or number of stars, and so on. Of course, stars and dogs do not have much common in a sense, but mathematics picks one property and focuses on that. In that sense, they are the same. A graph is a mathematical object that only cares about the relationship between nodes. If you only see the nodes and edges, they look dull and dry. At this point you need your imagination. These nodes can be: web pages, friends, cities, phones, oil bases, and so forth. They have the common property of individual objects that have relationships between them.
How can we write down the relationships between nodes? Being able to writing this down is important. If we have a method to represent a graph by writing it down, then we can store them. Especially if we have a unique representation (a notation) of a graph, we can ``compare'' two graphs. It is a difficult problem to compare arbitrary graphs. To make this problem simpler, the order of node should be unique. For instance, if each node has a unique name or number then we can sort the nodes of a graph. If the relationship is the same between two graphs, these graphs have the exactly the same notation. The next section describes how we could write down a description of a graph to be able to compare them.
So, the next blog, I will show you how to write down a graph.