Grafo Direcionado e Orientação
Definição: Dígrafos
Um grafo direcionado (ou dígrafo) é um par $(V,E)$ de conjuntos disjuntos (de vértices e arestas) junto com dois mapas $init : E \to V$ e $ter : E \to V$ atribuindo a cada aresta $e$ um vértice inicial $init(e)$ e um vértice terminal $ter(e)$. Diz-se que a aresta $e$ é direcionada de $init(e)$ para $ter(e)$. Observe que um grafo direcionado pode ter várias arestas entre os mesmos dois vértices $x,y$. Tais arestas são chamadas arestas múltiplas; se eles tiverem a mesma direção (digamos de $x$ para $y$), eles são paralelos. Se $init(e) = ter(e)$, a aresta $e$ é chamada de laço.
Definição: Grafos Orientados
Um grafo direcionado $D$ é uma orientação de um grafo (não direcionado) $G$ se $V(D)=V(G)$ e $E(D)=E(G)$, e se $\{init(e), ter(e)\} =\{x,y\}$ para cada aresta $e=xy$. Intuitivamente, tal grafo orientado surge de um grafo não direcionado simplesmente direcionando cada aresta de uma de suas extremidades para o outro. Em outras palavras, grafos orientados são grafos direcionados sem laços ou arestas múltiplas.