Connectivity in Graphs
(Page 1 of 4 )
Think outside the box. This is the motto for today. Today, using graphs, we will find out how much of a threat just the elimination of a military base poses to us. For a precise calculation of this, we will use the Ford-Fulkerson algorithm and modify it for our needs by using the motto of the day. This article is the twelfth part of a thirteen-part series that shows how to use graphs and algorithms to solve everyday problems.
Did I just mention the Ford-Fulkerson algorithm? If you arrived here to learn that, you are just a little late. In the previous article, I presented everything you should know about the algorithm itself.
In case you missed it, you absolutely have to dig it up and become familiar with the algorithm if you wish to understand this article. I mean that seriously; do not read on if you do not know the algorithm.
Take a break and come back later once you comprehend it. You are in danger of not understanding a word of mine if you ignore this.
Now that we have that straight, you can begin to see how we'll use the lesson from the previous article. First, I am going to present how to bypass small obstacles, such as if we have many sources or many terminals, or what if the node itself has a given capacity?
I will follow up this presentation closely with the idea of solving the issue of k connectivity (related to edges) or k vertex connectivity, and illustrate this lesson with the scenario I alluded to in the introduction.
Next: Back to the Basics >>
More Code Examples Articles
More By Gabor Bernat
