Grafo orientado

Um arco e = ( x , y ) {\displaystyle e=(x,y)} é considerado ser direcionado de x {\displaystyle x} para y ; {\displaystyle y;} y {\displaystyle y} é chamado de cabeça e x {\displaystyle x} é chamado de cauda do arco; y {\displaystyle y} é dito ser um sucessor direto de x , {\displaystyle x,} e x {\displaystyle x} é dito ser um predecessor direto de y . {\displaystyle y.} Se um caminho composto por um ou mais arcos sucessivos leva de x {\displaystyle x} para y , {\displaystyle y,} então y {\displaystyle y} é dito ser um successor de x , {\displaystyle x,} e x {\displaystyle x} é dito ser um predecessor de y . {\displaystyle y.} O arco ( y , x ) {\displaystyle (y,x)} é chamado de arco ( x , y ) {\displaystyle (x,y)} invertido. Um grafo direcionado G é chamado de simétrico se, para cada arco, que pertence à G, o arco invertido correspondente também pertence à G. Um grafo dirigido simétrico sem laços é equivalente a um grafo não orientado com os pares de arcos invertidos substituído por arestas, assim o número de arestas é igual ao número de arcos pela metade.

Para um nodo, o número de pontos de extremidade adjacente à cabeça de um nó é chamado de grau de entrada do nodo e o número de pontos de extremidade da cauda é o seu grau de saída. O grau de entrada é denotado deg − ⁡ ( v ) {\displaystyle \deg ^{-}(v)} e o grau de saída como deg + ⁡ ( v ) . . {\displaystyle \deg ^{+}(v)..} Um vértice com deg − ⁡ ( v ) = 0 {\displaystyle \deg ^{-}(v)=0} é chamado de fonte, uma vez que é a origem de cada uma das suas arestas incidentes. Da mesma forma, um vértice com deg + ⁡ ( v ) = 0 {\displaystyle \deg ^{+}(v)=0} é chamado de sumidouro (ou poço). A fórmula da soma dos graus afirma que, para um grafo direcionado Se para cada nodo, v ∈ V, deg + ⁡ ( v ) = deg − ⁡ ( v ) , {\displaystyle \deg ^{+}(v)=\deg ^{-}(v),} o grafo é chamado de digrafo balanceado.

Um digrafo G é chamado de fracamente conectado (ou apenas conectadop. 19) se o grafo subjacente não-direcionado obtido através da substituição de todas as arestas de G por arestas não direcionadas é um grafo conexo. Um digrafo é fortemente conectado ou forte se ele contém um caminho orientado de u a v e um caminho orientado de v a u para cada par de vértices u,v. Os componentes fortes são os subgrafos máximo fortemente conectados.

Um digrafo acíclico é um grafo direcionado sem ciclos direcionados. Uma árvore enraizada naturalmente se define como um digrafo acíclico, se todas as arestas da árvore subjacentes são dirigidas para longe da raiz. Um torneio é um grafo orientado obtido ao se escolher uma direção para cada aresta em um grafo completo não-direcionado. Na teoria dos grupos de Lie, um quiver Q é um grafo direcionado servindo como o domínio do e, portanto, caracterizando a forma de, uma representação V definida como um functor, mais especificamente um objeto da categoria functor FinVctKF(Q) onde F(Q) é a categoria livre em Q constituída por caminhos em Q e FinVctK é a categoria de espaços vetoriais de dimensão finita sobre um campo K. Representações de um quiver rótulam seus vértices com espaços vetoriais e suas arestas (e, portanto, caminhos) de modo compatível com transformações lineares entre eles, e transformam através das transformações naturais.