Graphs connectivity tells us how many edges or vertices must be removed from a graph so that the graph becomes disconnected. This induces the notations of the edge and vertex connectivity of a graph. In this thesis, I will first present some of the theorems related to graph connectivity. Then I will describe algorithms for checking whether or not a graph is connected, which can also be used to check whether or not a graph has been successfully split. Next, I will show how the min-cut problem is solved using the algorithm for maximum flow. Then, I will continue with presentation of some advanced and more adapted algorithms for the considered problem. Finally, I will conclude the thesis with a summary of the key findings. The thesis is thus a basic overview of the problem of graph connectivity.
|
