# Introduction to Graphs

Learn about graphs, their applications, and their operations.

## We'll cover the following

## 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.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy