In this section, we introduce another useful variant of a graph. In a graph, the existence of an edge $xy$ can be used to model a connection between $x$ and $y$ that goes in both ways. However, sometimes such a model is insufficient. For instance, perhaps it is possible to fly from Atlanta directly to Fargo but not possible to fly from Fargo directly to Atlanta. In a graph representing the airline network, an edge between Atlanta and Fargo would lose the information that the flights only operate in one direction. To deal with this problem, we introduce a new discrete structure. A digraph $\bfG$ is a pair $(V,E)$ where $V$ is a vertex set and $E\subset V\times V$ with $x\neq y$ for every $(x,y)\in E\text{.}$ We consider the pair $(x,y)$ as a directed edge from $x$ to $y\text{.}$ Note that for distinct vertices $x$ and $y$ from $V\text{,}$ the ordered pairs $(x,y)$ and $(y,x)$ are distinct, so the digraph may have one, both or neither of the directed edges $(x,y)$ and $(y,x)\text{.}$ This is in contrast to graphs, where edges are sets, so $\{x,y\}$ and $\{y,x\}$ are the same.
Diagrams of digraphs use arrowheads on the edges to indicate direction. This is illustrated in Figure 12.12. For example, the digraph illustrated there contains the edge $(a,f)$ but not the edge $(f,a)\text{.}$ It does contain both edges $(c,d)$ and $(d,c)\text{,}$ however.
When $\bfG$ is a digraph, a sequence $P=(r=u_0,u_1,\dots,u_t=x)$ of distinct vertices is called a directed path from $r$ to $x$ when $(u_iu_{i+1})$ is a directed edge in $\bfG$ for every $i=0,1,\dots,t-1\text{.}$ A directed path $C=(r=u_0,u_1,\dots,u_t=x)$ is called a directed cycle when $(u_t,u_0)$ is a directed edge of $\bfG\text{.}$