Connectivity in Graphs - K Connectivity
(Page 3 of 4 )
There are two types of connectivity in graphs, connectivity of the edges and connectivity of the vertexes. Whenever we talk about connectivity, we first refer to it as of the edges. When we want to talk about vertexes, we need to talk about K Vertex Connectivity. What is covered under this name?
Connectivity refers to the fact that there exists a road between any two nodes. K Connectivity says that, if we eliminate any number less than k of that type of component (any one) from the graph, we will still get a connected graph. Of course, if we eliminate vertexes we also delete the edges related to them.
So how does this tie in with a war in Vietnam? Let there be n military bases. Each one of them can communicate with a specific number of other bases. The connections build up a graph with directed edges inside it. The connections can be mutual; if this is the case, we can just add an edge in both directions.
The information arrives at headquarters that the enemy has eliminated k military bases. The question is, can we remain calm, considering the way that our bases can connect with the other remaining bases? This is node connectivity. We can imagine a case when the edges are relevant. For instance, we talk about roads, and if k instances of them got bombed, could we still reach all the cities?
From the definition you can already see that the connectivity of nodes is a much more serious trait than of vertexes, and we will see immediately why this is true. From the definition of connectivity, we can sense that we are talking about individual roads. In order for us to still be able to reach a point when an edge or vertex is eliminated, we must have an alternative road we can use to get there.
Connectivity in fact hides the number of individual roads between a point and all the rest inside the graph. In the case of edge connectivity we are talking about different edges, while in the case of node connectivity, the vertexes through which the road passes have to be different.
So the source will be the vertex itself, which we are observing, while the terminal handles all the ends. The algorithm is simple. Consider the graph and iterate through every different vertex pair. Let every edge have a capacity of one. Call the Ford-Fulkerson algorithm for each pair to calculate the number of different (alternative) roads.
If the capacity is the maximum flow that can travel through, the graph will be just like this. All that we have to do is to pick the smallest number from this, and that will tell us how many edges we can delete and still be able to contact any military base. Note that we can pick for removal any one of the edges, not just a collection of them, as long as we choose k number of them.
Here it is all this implemented in C code. We need to reset the current flow number to zero before each call.
int kConnectedEdge(Vertex**& neighborMatrix, Node*& list, const int& n)
{
int i = 0, j = 0, curKCon = 0;
int k = INFINITY;
for( i=1; i <= n-1; ++i)
for( j=i+1; j<= n; ++j)
{
int a =0, b = 0;
for (a = 1; a <= n; ++a)
for (b = 1; b <= n ; ++b)
{
neighborMatrix[a][b].flowValue = 0;
}
curKCon = Ford_Fulkelson(neighborMatrix, list, i , j, n);
if (curKCon < k)
{
k = curKCon;
}
}
return k;
}
Here is an example graph:
With our algorithm, all this will look as follows, as we need to double every edge and add the direction to them:
The result in the output file is correct:
The input graphs edge connectivity is 3
Next: The k Node Connectivity >>
More Code Examples Articles
More By Gabor Bernat
