I studied applied mathematics, in which I did both a bachelor's and a master's degree.
The Basics of Graph Theory
A graph is a pair of sets (V,E) where V is the set of vertices and E is the set of edges. E consists of pairs of elements of V. That means that for two points v and w in V the pair (v,w) is contained in E if there is an edge between v and w in the graph. A graph can be drawn in the plane. We call this an embedding of the graph in the plane. If this is possible to do in such a way that no edges cross each other the graph is called planar. Such an embedding is called a plane embedding of the graph.
Graphs can be used to model all kinds of things. It is mostly associated with networks. This can be a network of cities that are connected via roads, but also a network of people where an edge is drawn between two people if they know each other. Graph theory has a lot of real world applications. To be able to understand these applications you need to understand some terminology.
The vertices and edges are already discussed. Another important concept is the concept of a face. A face is a connected region in the plane that is surrounded by edges. Easier said, it is a region of the plane of which you can go from a point in the face to any other point in the face without crossing an edge. Vertices, edges and faces have a relationship which is described by the formula of Euler:
V + E – F = 2
Here V is the number of vertices, E the number of edges and F the number of faces. Keep in mind that the in this formula the region outside the graph is also denoted as a face, which seems maybe counterintuitive, but if you look at the definition of a face it is logical. This formula can come up very handy when trying to prove properties of certain graphs.
Special Types of Graphs
Directed and Undirected Graphs
A graph van be directed and undirected. A directed graph is a graph in which the edges have directions. In this case, they are often called arcs. This means that it can come up that there are two arcs between two vertices. One for each direction. Strictly speaking this can also happen in an undirected graph, but in practice this does not happen normally. A directed graphs is sometimes also called a digraph.
There are weighted and unweighted graphs. In a weighted graphs weights are associated with the edges. This can refer to the length of the connection or the costs to use this connection for example. Both directed and undirected graphs can have weights.
In the complete graph every vertex is connected with an edge to all other vertices. When the graph has five or more vertices it is not planar. For one to four vertices it is planar.
A bipartite graph is a graph in which the set of vertices can be divided in two disjoint sets such that there are no edges between vertices of the same set.
A graph is called regular If the degree of every vertex is equal. This means that every vertex has the same number of neighbours. If in a regular graph all two adjacent vertices share an equal number of neighbours the graph is considered to be strongly regular.
Problems and Applications of Graph Theory
There are many types of problems that can be solved in graph theory. We will list a couple here. The first is colorings. In this problem the goal is to color all vertices of a graph such that no two adjacent vertices have the same color with the least amount of colors as possible. When the graph is planar it has been proven that this can be done with at most four colors for every graph. When the graph is not planar this is not the case anymore. For example the complete graph of five vertices needs five colors. An example of a real world application of graph colorings is making timetables. Every job gets a vertex. If two jobs cannot be done in the same time slot we will connect them with an edge. Now the minimum number of colors needed, also called the chromatic number, corresponds to the minimum number of time slots needed to schedule all the jobs.
Another important class of graph problems are routing problems. Finding the shortest path in a weighted graph is a very important problem that has a lot of real world applications. For example when the vertices are cities and the edges correspond to roads between the cities. The weights represent the lengths of the roads. Dijkstra’s algorithm finds the shortest path between two vertices in a very efficient way. This is the basis for a lot of real world applications. But there are many more applications of routing problems, for example the minimum spanning tree problem. The goal is to find a minimum total weight set of connections between the vertices such that there is a path from every vertex to every other vertex of the graph. This can be done efficiently with Kruskal’s algorithm or Prim’s algorithm. A real world application of this is the electricity net between hubs. There are many possible connections but not all are needed. Picking the connections of the minimum spanning tree will minimize the costs.
Also flow problems can be solved with graph theory. In a flow problem we have one vertex that is the source and one that is the sink. Now we assign capacities to all edges. Each edge can get a flow, which is comparable to a weight, but it cannot exceed the capacities. There are efficient algorithms to calculate the maximum flow from the source to the sink and they can also determine which connections have to be used in order to reach this flow. This also has numerous real world applications. For example modeling fluids through pipes, but also streams of resources within a production process.