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{.}$$