Graph

• Adjacency List / Adjacency Matrix
• Undirected Graph
• Directed Graph
• Max Flow Problem / Minimum cut
• Spanning tree

Adjacency List / Adjacency Matrix

There are 2 ways to implement a graph which are "Adjacency List" and "Adjacency Matrix". Adjacency list uses hash map (and array) and Adjacency Matrix uses 2 dimension array. Both of them represent graph data structure yet space complexity is different.

Adjacency list uses array and map which a key on map represents a vertex and its value is array which contains adjacency vertices. It is number of vertices plus edges equal to θ(V+E).

Adjacency Matrix uses 2 dimension array (matrix) to represent vertices and edges so that θ(n²).

Which is better?

Depends on density of the graph and operation you want to do. Adjacency List is good for graph search.

Undirected Graph

Undirected graph can have (n-1) edges at minimum and n(n-1) / 2 edges at most in the case of not having parallel edges.

Directed Graph

Sparse graph

Spare graph is the graph that the number of edges is O(n). (n is the amount of vertices).

Dense graph

Dense graph is the graph that the number of edges is O(n²).

Max Flow Problem

Max flow problem is finding maximum flow on a graph (network) from a node (s) to a node (t). Max flow can be calculated by finding minimum cut because of this theorem(s,t) - max flow = (s,t) - minimum cut. s and t represent the entry node and end node.

Usage

• Identify the weakness in your network.
• community detection in social network
• image segmentation

Minimum Cut

"cut" is a partition of the vertices of a graph into two disjoint subsets that are joined by at least one edge.

There are crossing edges from tail to head and Minimum cut algorithm is to identify the number of crossing edges.

In this algorithm parallel edge is allowed.

The combination of cuts graph with n vertices can is 2ⁿ - 2 (- empty set cases) cuts. A graph has 2 vertices can have 2 cuts out of 2 cuts combination and 3 vertices can have 2 cuts out of 6 cuts combination.

http://even-eko.hatenablog.com/entry/2013/08/08/224430

https://research.preferred.jp/2011/05/randomized-min-cut/

http://even-eko.hatenablog.com/entry/2013/08/08/195120

Karger algorithm (Random Contraction algorithm)

Random Contraction algorithm is reducing vertices until the number of vertices get down to 2.

While there are more than 2 vertices:

• pick a remaining edge (u,v) uniformly at random

• merge (or “contract” ) u and v into a single vertex

• remove self-loops return cut represented by final 2 vertices.

Probability of crossing choosing

We can not choose crossing edges because choosing crossing edges fuses two sets so that we need to avoid it. What is the probability of choosing crossing edges? It is k (number of edges crossing min cuts) / m (total number of edges) at first iteration.

Ford-Fulkerson algorithm

Topological sort

Topological sort is sorting a graph in order of directions.

Strongly Connected Components

Strongly Connected Components is a group of directed acyclic graph. It is only valid directed edge from any vertex to every other vertex.

https://www.hackerearth.com/ja/practice/algorithms/graphs/strongly-connected-components/tutorial/

Kosaraju's algorithm

Two DFS Time complexity O(m+n) and flip direction of the edges at second call.

First, simple DFS and add leader (index) to each vertices in order of depth.

Second of all, flip all edges and DFS from shallowest node whose leader(index) is largest. If it is cyclic, the group of nodes are connected component and move to the second largest leader(index)

DFS()

connected_component()