Authors in a Markov matrix: Which author do people find most inspiring? (6)

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 authors

Assume we are describing the following authors:

• William Shakespeare
• Lewis Carroll
• Raymond Smullyan
• Martin Gardner

There could be many different opinions about what kinds of relationships these authors have. Here I assume Shakespeare inspires Carroll, and Carroll inspires Smullyan and Gardner. Such graph can be shown in Figure 6.

Figure 5. Graph example 1. Each node is an English author.

Example 2: Nodes represent train stations

Assume each node represents a train station. The followings are stations in Berlin, Germany.

• Weinmeisterstr
• Alexanderplatz
• Hackescher Markt
• Jannowitzbruecke

When two stations are next to each other (the next station), we connect them with an edge that represents a ``neighbor'' relation. The graph is shown in Figure 7. By the way, the S-Bahn (city train) in Berlin is frequently under construction and some intervals may sometimes have no train service, or may only have service in one direction. (The other direction usually has a bus connection.)  When the train only goes in one direction, the graph should use directed edges.

Figure 7. Graph example 2. Each node is a train station.

There is one important thing to note here. Whatever a node represents, the shape of these graphs of Figure 4, 5, 6, 7 (Figure 4, 5 are found the former blog entry) are the same shape. The structure of the graphs are identical. When the structure of the graphs is the same, we consider they are the same graph in mathematics. Despite the meaning of the nodes, graph theory only considers the structure of the graph.

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.