Introduction to Graphs

Graphs overview

In this module, we study two representations of graphs and basic algorithms that use these representations.

Mathematically, a (directed) graph is a pair $G = (V ,E)$ where $V$ is a set of vertices and $E$ is a set of ordered pairs of vertices called edges. An edge $(i,j)$ is directed from $i$ to $j$; $i$ is called the source of the edge and $j$ is called the target. A path in $G$ is a sequence of vertices $v_0,..., v_k$ such that, for every $i \in \{1,...,k\}$, the edge $(v_{i−1}, v_i)$ is in $E$. A path $v_0,..., v_k$ is a cycle if, additionally, the edge $(v_k , v_0)$ is in $E$. A path (or cycle) is simple if all of its vertices are unique. If there is a path from some vertex $v_i$ to some vertex $v_j$, then we say that $v_j$ is reachable from $v_i$. An example of a graph with twelve vertices is shown below. Vertices are drawn as numbered circles and edges are drawn as pointed curves pointing from the source to the target.