mincut

Input - An undirected graph G = (V,E) (note that parallel edges are allowed) Goal - Tom compute a cut with fewest number of crossing edges (a min cut) The minimum cut problem or min-cut problem is to determine the cut which has the least number of crossing edges. Please note that to understand mincut, you have to first read what is cut, if you don’t alreadyy know that. So, consider the following graph - [Read More]

Graphs consist of 2 ingredients : Vertices (V) , also called nodes and can be pictured as dots Edges (E) , the line connecting the nodes. Types of Graphs Depending on the edges, there two types of graphs: Undirected Graphs - A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the ‘Family tree of the Greek gods’ **Directed Graphs (**aka Arcs) - Directed Graph: A graph that entail edges with ordered pair of vertices and has direction indicated with an arrow. [Read More]