Graphs

Graph

Formally, a simple graph is a pair of sets $(V,E)$, where $V$ is an arbitrary non-empty finite set, whose elements are called vertices or nodes, and $E$ is a set of pairs of elements of $V$, which we call edges. In an undirected graph, the edges are unordered pairs or just sets of size two; we usually write ${uv}$ instead of $\left\{ u, v \right\}$ to denote the undirected edge between $u$ and $v$. In a directed graph, the edges are ordered pairs of vertices; we usually write $u\rightarrow v$ instead of $(u, v)$ to denote the directed edge from $u$ to $v$.

Following standard (but admittedly confusing) practice, we will also use $V$ to denote the number of vertices in a graph and $E$ to denote the number of edges. Thus, in any undirected graph, we have $0 ≤ E ≤ \binom{V}{2}$, and in any directed graph, we have $0 ≤ E ≤ V (V − 1)$.

The endpoints of an edge $uv$ or $u\rightarrow v$ are its vertices $u$ and $v$. We distinguish the endpoints of a directed edge $u\rightarrow v$ by calling $u$ the tail and $v$ the head.

The definition of a graph as a pair of sets forbids multiple undirected edges with the same endpoints or multiple directed edges with the same head and the same tail. (The same directed graph can contain both a directed edge $u\rightarrow v$ and its reversal $v\rightarrow u$.) Similarly, the definition of an undirected edge as a set of vertices forbids an undirected edge from a vertex to itself. Graphs without loops and parallel edges are often called simple graphs; non-simple graphs are sometimes called multigraphs. Despite the formal definitional gap, most algorithms for simple graphs extend to multigraphs with little or no modification, and for that reason, we see no need for a formal definition here.

For any edge $uv$ in an undirected graph, we call $u$ a neighbor of $v$ and vice versa, and we say that $u$ and $v$ are adjacent. The degree of a node is its number of neighbors. In directed graphs, we distinguish two kinds of neighbors. For any directed edge $u\rightarrow v$, we call $u$ a predecessor of $v$, and we call $v$ a successor of $u$. The in-degree of a vertex is its number of predecessors; the out-degree is its number of successors.

A graph $G^′ = (V^′,E^′)$ is a subgraph of $G = (V,E)$ if $V^′ ⊆ V$ and $E^′ ⊆ E$. A proper subgraph of $G$ is any subgraph other than $G$ itself.

Walk and path

A walk in an undirected graph $G$ is a sequence of vertices, where each adjacent pair of vertices is adjacent in $G$; informally, we can also think of a walk as a sequence of edges. A walk is called a path if it visits each vertex at most once. For any two vertices $u$ and $v$ in a graph $G$, we say that $v$ is reachable from $u$ if $G$ contains a walk (and therefore a path) between $u$ and $v$. An undirected graph is connected if every vertex is reachable from every other vertex. Every undirected graph consists of one or more components, which are its maximal connected subgraphs; two vertices are in the same component if, and only if, there is a path between them.

A walk is closed if it starts and ends at the same vertex; a cycle is a closed walk that enters and leaves each vertex at most once. An undirected graph is acyclic if no subgraph is a cycle; acyclic graphs are also called forests. A tree is a connected acyclic graph or, equivalently, one component of a forest. A spanning tree of an undirected graph $G$ is a subgraph that is a tree and contains every vertex of $G$. A graph has a spanning tree if, and only if, it is connected. A spanning forest of $G$ is a collection of spanning trees, one for each component of $G$.

Directed graphs require slightly different definitions. A directed walk is a sequence of vertices $v_0 \rightarrow v_1\rightarrow v_2\rightarrow · · · \rightarrow v_l$ such that $v_{i−1}\rightarrow v_i$ is a directed edge for every index $i$; directed paths and directed cycles are defined similarly. Vertex $v$ is reachable from vertex $u$ in a directed graph $G$ if, and only if, $G$ contains a directed walk (and therefore a directed path) from $u$ to $v$. A directed graph is strongly connected if every vertex is reachable from every other vertex. A directed graph is acyclic if it doesn’t contain a directed cycle; directed acyclic graphs are often called dags.