Graph Theory (II)

It is now time to move away from the introductory posts, and delve deeper into specific topics. Being a graph theorist myself, I decided to make Graph Theory my first non-introductory post.
(For the introductory post to this field, please read this post.)

In the previous post on this topic, I finished with certain questions one can ask about graphs. The first of these is about the connectivity of graphs. Namely, the question is, given two vertices u and v in a graph, can we find some way to get from u to v, following edges in the graph? This is a very easy problem to visualise. If a graph is made up of two or more parts (known as components), then it is impossible to get from a vertex in one component to a vertex in another component. We say that the graph is disconnected. Now, let's say that for every pair of vertices u and v in a graph, you can find some path u, x1, x2, ... , v which moves through consecutively adjacent vertices x1, x2 and so on. Then there cannot be more than one component in the graph and we say the graph is connected.

This question of connectivity can be easily extended in two important ways. The first one deals with the best way to get from one vertex to another. Let's say that the vertices correspond to cities and the edges to roads connecting them. Now, for simplicity, let's say that each edge costs you 5 euros in gasoline. Then, to minimise your costs, you will want to find the path that uses the fewest edges. Going from Munich to Bologna and from there to Paris is possible, but it is generally much cheaper to go as directly as you can. This leads to the idea of the shortest path. That is, given vertices u and v in a graph, what is the shortest path between them? Clearly, for any two vertices, if you can find some path between them, a shortest path must also exist. This is because paths have non-negative length, so you cannot reduce path length indefinitely. One of the most well-known methods for finding shortest paths is Dijkstra's Algorithm. The way it works is by searching for the shortest path from the starting vertex u to every other vertex. This is done by splitting the graph into two parts: the explored vertices and the unexplored vertices. Additionally, for every vertex v, the algorithm maintains a tentative distance from u to v. Initially, only the starting vertex is explored. At each step, the algorithm picks the unexplored vertex with the shortest distance and explores it. Whenever a vertex v is explored, the algorithm attempts to find a shortest path from u to the neighbours of v, by incorporating v. If a path shorter than what was available before can be found, these neighbours are updated accordingly.

The reason this algorithm works, is that the shortest path between two vertices is made up of other shortest paths. That is, if the shortest path from u to v goes through x, then it contains the shortest path from u to x, followed by the shortest path from x to v. The algorithm seeks all such shortest subpaths and picks the best available one.

The second way in which connectivity can be extended is with the notion of k-connectivity. Let's say there are several path between two vertices, u and v. If we were to remove some vertices from the graph (and all the edges that go with them) would there still be a path between u and v? How many vertices make it impossible for us to find such a path? What about removing edges? The ideas of connectivity are important in various problems of resource management. Suppose you have to provide internet service to some locations. You would use various connecting stations, which would handle the traffic of information and route it from place to place. But what if some of these stations were to be damaged? Could your network cope? And how many stations can you safely shut down at a time for maintenance, without compromising the quality of your service? As you can see, the question of connectivity is very important for proper resource management.