Notation for Graphs
Here we collect notation related to graphs and various related objects.
Basic Graph Notations and Definitions
| Notation | Meaning |
| $G=(V,E)$ | Graph $G$ on set of vertices (or nodes) $V$ and set of edges $E\subseteq V\times V$. |
| $n$ | Number of nodes, same as $|V|$. |
| $m$ | Number of edges, same as $|E|$. |
| Undirected graph | $G=(V,E)$ is undirected if $(u,w)\in E$ necessarily implies $(w,u)\in E$ (and vice-versa). By default all graphs are undirected. |
| $u-w$ path | A sequence of nodes $u=u_1,u_2,\dots, u_k=w$ such that for every $i\in [k-1]$, $(u_i,u_{i+1})\in E$. |
| simple path | A path with no repeated nodes. |
| Cycle | A path $u_1,\dots,u_k$ is a cycle if (1) $u_1=u_k$, (2) $u_1,\dots,u_{k-1}$ are distinct, (3) For directed graphs $k\ge 3$ and for undirected graphs $k\ge 4$. |
| connected nodes | $u$ and $w$ are connected (for an undirected graph) if there is an $u-w$ path. |
| strongly connected nodes | $u$ and $w$ are strongly connected (for directed graph) if there is both an $u-w$ path and $w-u$ path. |
| Connected graph | An undirected graph is connected if every pair of nodes in $G$ are connected. |
| Strongly connected graph | A directed graph is strongly connected if every pair of nodes in $G$ are strongly connected. |
| Distance | Distance between $u$ and $w$ (in an undirected graph) is the length of the shortest $u-w$ path. |
| Tree | An undirected graph is a tree if (1) $T$ is connected and (2) $T$ has no cycles. |
| Child/parent | In a rooted tree, $u$ is the parent of $w$ (and $w$ is the child of $u$) if $(u,w)$ is an edge and $u$ is closer to the root than $w$. |
| $\text{CC}(s)$ | The connected component of $s$. |
| $n_u$ | The degree of vertex $u$ or the number of its neighbors, i.e. $n_u=|\{v|(u,v)\in E\}|$. |
| DAG | A directed graph that has no (directed) cycles. |
| $\text{In}_w$ | In-degree of vertex $w$ in directed Graph $G=(V,E)$, i.e. $\text{In}_w=|\{(u,w)\in E|u\in V\}|$. |
| $\text{Out}_w$ | Out-degree of vertex $w$ in directed Graph $G=(V,E)$, i.e. $\text{Out}_w=|\{(w,u)\in E|u\in V\}|$. |
Connectivity Algorithms
BFS
| Notation | Meaning |
| $s$ | $s$ is the start vertex for BFS |
| $L_j$ | $L_0=\{s\}$ and $L_j$ is the set of vertices not in $L_0,\dots,L_{j-1}$ but are connected by an edge to some vertex in $L_{j-1}$. |
| BFS tree | The tree implicitly "traced out" by a BFS run. The root is $s$ and then layer $L_j$ is "level" $j$ in the BFS tree. |
Explore
| Notation | Meaning |
| $s$ | $s$ is the start vertex for the Explore algorithm |
| $R$ | The current set of vertices that have been found to be reachable from $s$ by the Explore algorithm. |
| $R^*$ | The final set $R$ that is output by the Explore algorithm. |