### Graphs

========

Introduction

In its most formal definition, A graph is a set of vertices and edges. In Computer science, it is a data type used to represent relationships or connections.

Examples: Road Networks, The Web, Social Networks, Precedence Constraints, Biological Structures, Computer chip design etc.

A Graph has two main ingredients:

• Vertices (set of vertices is represented by ‘V’ generally in Algorithms).
• Edges (pair of vertices, set of edges is represented by ‘E’ generally).

Types

There are two types of graphs mainly:

• Directed - A graph where the vertices are unordered pairs for a given edge. ###### source: slide from Design and Analysis of Algorithms course by Tim Roughgarden on coursera.
• Undirected - When vertices are an ordered pair. ###### source: slide from Design and Analysis of Algorithms course by Tim Roughgarden on coursera.

So that was a sort of refresher to graphs for those who are familiar with it already. Those who are very unfamiliar with the term should consider reading about them first.

### Cuts

=====

Definition

A cut is a partition of the vertices of a Graph into two non-empty sets A and B.

For example, if G(V, E) is a graph then a cut will devide V into two non-empty sets where some edges will remain in either A or B and some will cross the cut (crossing edges).

Examples:  1. Directed Graph 2. Undirected Graph

### The Minimum Cut

===================

Problem Definition:

In Graph Theory, the minimum cut problem is to find a cut with minimum number of crossing edges.

Use of a Minimum Cut

There are many applications of the minimum cut. Few are listed below:

• Identifying Network Bottlenecks.
• Community detection in Social Networks.
• Image Segmentation.
• In recommendation systems.

How to find a minimum cut

Here is the Karger’s algorithm to compute a minimum cut in a given graph.

``````while number of vertices > 2:
- pick a remaining edge(u, v) uniformly at random
- merge u and v into a single vertex
- remove self-loops
return cut represented by final 2 vertices
``````

Now, I can’t share the code due to some reasons. But I will try to elaborate using pseudocode.

``````make adjacency list for the graph:
graph = []
for every vertex:V in graph:
graph.append(V, all adjacent vertices of V)

find min_cut:
copy(graph)
while length of graph > 2:

choose a random index                : selecting random edge
capture first and second element of index row
merge the captured elements into one : This is our contraction stage

for every vertex:V in graph:
if V is the second captured element:
remove the row for V
if first captured element in V:
remove first captured element
if second captured element in V:
remove second captured element
if first or second captured element were removed:
V.append(merged vertex)

pick the min(left two vertex lists):List
for each element:E in List:
sum(ocurrences of E)

sum_of_occurences - len(List)
``````

That’s it.

This will give the minimum number of cuts a given graph can have. The algorithm is randomized so it requires 3-4 continuous runs to find the exact answer. This algorithm can be used for many applications along with the few mentioned above.