Graph Theory

Graph Theory is the study of graphs, which are mathematical structures used to model pairwise relation between objects. A graph in this context is made up or vertices(also referred to as nodes or points) which are connected by edges (also referred to as links or lines).

Directed Graph

A Directed Graph is a graph that is made up of a set of vertices that are connected by directed edges, also refereed to as arcs.

Strongly connected component

A graph is said to be strongly connect if every vertex is reachable from every other vertex. The strongly connect components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find it’s strongly connected components, in linear time ($\Theta(V+E)$)

Algorithms for strongly connect components

Kosaraju’s Algorithm

TODO(tlc): fill this in