Sunday, April 29, 2012

Graph Theory

We come now to my own personal field of interest, the subject of graph theory. This has nothing to do with pie charts or bar graphs; these are a different kind of graph.

Formally, a graph is a special type of mathematical structure, composed of two parts. The first part is a set, a collection of distinct elements called vertices or nodes. The second is a collection of 2-tuples of the vertex set. These 2-tuples are the edges. Visually, we represent a graph as a network. The vertices are points and the edges are lines connecting these points. More specifically, we are usually interested in graphs with a finite vertex set and where the edges are distinct and connect distinct vertices. The networks we draw for these graphs will have at most one edge between two vertices and no loops on any single vertex.

Graph theorists are interested in many different characteristics of graphs. The reason these characteristics are studied is that there are many applications to real world problems which are more easily solved with graphs. For example, computer networks could not run smoothly and successfully without a proper understanding of graph theory, resource allocation problems become much harder to solve and so on and so forth.

The biggest problem for students learning graph theory is its apparent lack of connectivity to other mathematical topics. More often than not, students have a background that is (perhaps detrimentally) over-abundant in calculus (or rather, the techniques of calculus) and therefore lack a proper foundation in more fundamental branches of Mathematics, including set theory. This means that they will be bombarded with several new definitions and almost none of them will be present in their mathematical background; they will have no previous knowledge to draw upon, to help them understand these new topics. In this post (and hopefully future ones), I will attempt to give these definitions in a slower, more relaxed pace, than a graph theory course would require. Perhaps this method would be best suited for a two semester graph theory course, but that is neither here nor there.

We first consider the idea of measuring things about a graph. How large or small a graph is can depend on what we are using it for. The two most generals ways in which we measure graphs are the number of vertices it has (known as the order of the graph) and the number of edges it has (known as the size). For example, if you look at a map of, say, major motorways and represent these motorways as edges in a graph, the size of the graph will be the number of motorways you have. On the other hand, the order will be the number of destinations (cities for example) that are connected by these motorways. The order and size of a graph, give us an idea of how large our graph is. They also tell us other things, like how dense or sparse a graph is. For example, if a graph has 10 vertices, the largest number of edges it can possibly have is 45. If we have a graph with 10 vertices and only 15 edges, this could be considered a very sparse graph. If on the other hand it had 40 edges, this would be a very dense graph. The ideas of density and sparsity become more important when other measurements are made on graphs, but they're interesting enough on their own as well.

The next simplest definition we can give for graphs is that of adjacency. We say that two vertices are adjacent (or neighbouring), if there is an edge between them. That is, if we have an edge connecting the vertices u and v, then u and v are adjacent. We also say that v belongs in the neighbourhood of u (and vice-versa). In computer networking, if we take a graph of connections in a serve-client model, we could say that a server is adjacent to the clients it is connected to.

It is often the case that we want to know how many neighbours a vertex has (usually because we want to minimise them or maximise them). The number of neighbours of a vertex u, or the number of vertices adjacent to u, is denoted as d(u) and is known as the degree of u. Vertices with many neighbours will have a high degree. In the server-client model, the degree of each server is the number of clients it connects to.

Clearly, there are many more questions one can ask about graphs. (Is there a way to get from a certain vertex to another, following the edges between adjacent vertices? Is there a way to start at some vertex in a graph, and go through every edge exactly once, going sequentially through adjacent vertices? How many colours do we need to colour the countries of a map, so that no neighbouring countries share the same colour?) However, this post is a mere introduction to the idea of what a graph is, and will not delve any deeper into the theory. Perhaps in future posts, I will try to answer these and other questions about graphs.