Connectivity in Graphs - Back to the Basics
(Page 2 of 4 )
When we work with flow networks, sometimes the requirements for the Ford-Fulkerson algorithm are simply not satisfied. To work with the algorithm, we need a single source and a single terminal. The vertexes are just connection points, and they cannot have capacities. Also, remember that we used directed edges.
However, if we make a little modification to our input graph, we can transform it into graphs that have all the upper traits. We can get rid of the issue with multiple sources and multiple drains if we add a new source and connect all the current sources to it. The capacity of the edges connected from the new point to the sources is infinity.
You can apply the same rule to the terminals also, but the direction of the edges is from the terminals to the new point. This way, we will have a single source and a single terminal. Run the algorithm on this graph and it will solve the problem for the multiple sources/terminals graph at the same time. Here is a picture to illustrate it:
Once we have a graph with edges that are not directed, the problem is easily solved by adding directed edges in both direction. However, once the equation includes nodes with capacity, this gets a little more complicated. Obviously we cannot call the algorithm with this input data, so we will first transform our graph into something that maintains the traits enumerated at the start of this page.
Consider that we have a graph with n vertexes. If every vertex has a capacity of c (v), all we need to do is extract the node out of an edge. To achieve this, add a new node to the graph. Connect an edge from the vertex in context to the newly-added one and let the capacity be equal to c (v).
It is a good idea to name the new vertex n+i, where "i" is the number of the node we just tried to extract. All of the incoming edges will maintain their connection to node I, while the outgoing edges will come from, instead of node "i," vertex n+i. Here is a picture that shows how to handle this example, to make everything clear:
Apply this to all the edges and you are done. Now we will look into connectivity of the graphs and the war in Vietnam. For this, we will use what we just figured out on this page.
Next: K Connectivity >>
More Code Examples Articles
More By Gabor Bernat
