When we are talking about math, one of the easiest things to come to mind is its capacity for prediction, to help people plan. And most of the time, it is indeed the case, with prominent problems in this field being those involving finding the shortest distance, which is very useful for urban planning and economics. An advanced field of mathematics, despite not specifically designed for this, was one of its most significant contributors. Yes, I’m talking specifically about graph theory, a seemingly simple yet infinitely intricate, and interesting thing to study about. Let’s take a look!
- What is a graph?
The formal definition goes like this, at least for an undirected, simple graph:
A graph is a pair G = (V, E), where V is a set whose elements are called vertices, and E is a set of two-sets of vertices, whose elements are called edges.
To make a simple definition, imagine a set of dots, some of them connected. Notice how V is not a set of vertices, it is a set whose elements are called vertices. This means that the dots, or the vertices, are just the representations of the actual elements inside the V set. Similarly, the edges are just representations of the elements inside the set E. This clears up a lot about how graphs are usually used – the elements that needed describing will be the vertices, while the relationship between them will be the edges.
Take an example of a party, in which people take handshakes with each other. To track the handshakes, we would simplify the whole party into a single graph, in which:
- V is the set of party attendants, each of whom is a vertex;
- E is the set of handshakes, each of which is an edge.
In this graph-building method, the relationship between two elements of set V is defined as the handshake, a quantity that we would like to obtain – and thus comes the definition of set E.
2. Directed vs Undirected graphs:
In the first ‘handshake’ example, we saw how a graph can be constructed to symbolize the relationship between individuals or elements. However, it is worth noticing that a handshake does not give particular care to whether a person is a giver or receiver of the relationship. Many times, the relationship that needs to be accounted for has clear-cut givers and receivers, in which case the undirected graph would not be the best indicator.
This is where directed graphs are used. Direct graphs are almost identical in definition to undirected graphs, except that instead of edges, we have vectors to represent the set E. Therefore, the set now has defined givers and receivers as the beginning and ending points of vectors.
Consider documenting a graph for the example below:
A country has 12 cities, all of which are connected either directly or via some cities in between. Every city, however, can be the beginning of a maximum of 6 fly routes to other cities. Is such a configuration possible, and how can it be done?
We immediately see that one of the preconditions, being the beginning of a maximum of 6 fly routes to other cities, requires the use of a directed graph – without which we could not possibly know which city is the beginning of the flight route. With that in mind, we would construct a graph like this:
- V is the set of cities, each of whom is a vertex;
- E is the set of flying routes, each of which is a vector.
That is currently all I have to say. I hope I will catch you next week with more elaboration on this topic. Until then, math on!
Crash on Maths 