Grafo orientado

miniatura| Un gráfico orientado sinxelo

En matemáticas, e máis concretamente na teoría de grafos, un **grafo orientado** (ou **grafo dirixido** ou **dígrafo**) é un grafo que está formado por un conxunto de vértices conectados por arestas orientadas, que son arestas onde se distingue un orixe dun final normalmente representado por unha frecha.

## Definición 
En termos formais, un grafo orientado é un par ordenado  onde 

* *V* é un conxunto cuxos elementos se chaman *vértices*, *nós* ou *puntos*;
* *A* é un conxunto de pares ordenados de vértices, chamados *arestas*, *arestas orientadas* (ás veces  chamado *E* en vez de *A*), *frechas* ou *liñas ou ligazóns dirixidas*.

Diferénciase dun grafo ordinario ou non orientado, en que este último defínese en termos de pares de vértices non ordenados, que normalmente se denominan *arestas*, *ligazóns* ou *liñas*.

## Tipos de grafos orientados 
### Subclases 
dereita|miniatura| Un grafo acíclico orientado sinxelo
dereita|miniatura| Un torneo en 4 vértices

* Os **Grafos orientados simétricos** son grafos orientados onde todosas arestas aparecen dúas veces, un en cada dirección (é dicir, para cada frecha que pertence ao dígrafo, tamén lle pertence a frecha inversa correspondente).
* Os **Grafos orientados sinxelos** son grafos orientados que non teñen bucles (frechas que ligan directamente os vértices consigo mesmos) e sen múltiples frechas cos mesmos nodos orixe e destino.
** Os **Grafos orientados completos** son grafos orientados simples onde cada par de vértices está unido por un par simétrico de arcos orientados (é equivalente a un grafo completo non orientado coas arestas substituídas por pares de arestas inversas).
** Os **Digrafos semicompletos** son digrafos simples onde hai un arco entre cada par de vértices. .
** Os **Digrafos cuasi-transitivos** son digrafos simples onde para cada tripla *x*, *y*, *z* de distintos vértices con arcos de *x* a *y* e de *y* a *z*, hai un arco entre *x* e *z*. Pode haber só un arco entre *x* e *z* ou dous arcos en direccións opostas. 
** Os **Grafos orientados simples** son grafos orientados que non teñen pares opostos de arestas orientadas (é dicir, como máximo un de  ou  poden ser frechas do grafo). Dedúcese que un grafo orientado é un grafo orientado puro se e só se non ten 2 ciclos. Este grafo pódese obter aplicando unha única orientación a un grafo non orientado.
*** **Torneos** son grafos orientados obtidos escollendo unha dirección para cada aresta en grafos completos non orientados. Un torneo é un digrafo semicompleto.
**** As *multiárbores* son DAG nos que non hai dous camiños orientados distintos desde o mesmo vértice inicial ata o mesmo vértice final.
**** As *árbores orientadas* ou *poliárbores* son DAG formadas ao orientar as arestas das árbores (grafos conexos, acíclicos non orientados).
***** As *árbores con raíz* son árbores orientadas nas que todas as arestas da árbore subxacente non orientadas están dirixidas cara a fóra ou todas cara á raíz. (chámanse, respectivamente, **arborescencias** ou ** árbores cara adentro**).

## Terminoloxía básica 
miniatura| Grafo orientado coa matriz de incidencia correspondente
Considérase que unha aresta  está orientado *de* *x* *a* *y*; *y* chámase *cabeza (ou orixe)* e *x* *cola (ou destino)* da aresta. Dise que *y* é un *sucesor directo* de *x* e *x* dise que é un *predecesor directo* de *y*. Se un camiño leva de *x* a *y*, entón dise que *y* é *sucesor* de *x* e *accesíbel* desde *x*, e que *x* é un *predecesor* de *y*. A aresta ou arco  chámase *arco invertido* de .

Unha representación matricial para un grafo orientado é a súa matriz de incidencia.

## Grao  de entrada e grao de saída 
miniatura| Un grafo orientado con vértices etiquetados (grao de entrada, grao de saída)
Para un vértice, o número de extremos de cabeza adxacentes a un vértice chámase *grao de entrada* do vértice e o número de extremos de cola adxacentes a un vértice é o seu *grao de saída* (chamado *factor de ramificación* nas árbores).

Sexan  e . O grao de entrada de *v* desígnase deg- (*v*) e o seu grao de saída denótase deg+ (*v*).

Un vértice con  chámase *fonte*, xa que é a orixe de cada un dos seus arcos de saída. Do mesmo xeito, un vértice con  chámase *sumidoiro*, xa que é o final de cada un dos seus arcos entrantes.

A *fórmula da suma de graos* indica que, para un grafo orientado,

: \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |E|.

Se para cada vértice , , o grafo chámase *grafo orientado equilibrado*. 

## Secuencia de graos 
A secuencia de graos dun grafo dirixido é a lista dos seus pares de graos de entrada e de saída; para o exemplo anterior temos a secuencia de graos ((2, 0), (2, 2), (0, 2), (1, 1)). A secuencia de graos é unha invariante do grafo orientado polo que os grafos orientados isomorfos teñen a mesma secuencia de graos. Porén, a secuencia de graos, en xeral, non identifica de forma única un grafo orientado; nalgúns casos, os dígrafos non isomorfos teñen a mesma secuencia de graos.

O problema de realización dun grafo dirixido é un problema de decisión na teoría de grafos. Dados os pares de números enteiros non negativos ((a_1,b_1),\ldots,(a_n,b_n)), o problema pregúntase se existe un grafo dirixido simple tal que todo vértice v_i ten grao de entrada a_i e grao de saída b_i.

## Conectividade dos grafos orientados 
Un grafo orientado é conexo (ou debilmente conexo ) se o *grafo subxacente* non orientado que se obtén substituíndo todas as arestas orientadas do grafo por arestas non orientadas é un grafo conexo.

Un grafoo orientado é  *fortemente conexo*  se contén un camiño orientado de *x* a *y* (e de *y* a *x*) para todo par de vértices . Os *compoñentes fortes* son os máximos subgrafos fortemente conexos.

Un grafo con raíz conexo (ou *grafo de fluxo*) é aquel no que existe un camiño orientado a cada vértice desde un *vértice raíz* distinguido.

## Notas 
## Véxase tamén 
### Bibliografía 
* (the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 ).
* .
* .
*  (the electronic 3rd edition is freely available on author's site).
* .
* Number of directed graphs (or directed graphs) with n nodes from On-Line Encyclopedia of Integer Sequences

### Outros artigos 
* Relación binaria
* Diagrama de fluxo
* Globular set
* Glosario de teoría de grafos
* Teoría de grafos
* Teoría de redes
* Orientación
* Preorde
* Ordenamento topolóxico
* Grafo transposto
* Problema do ciclo de peso cero
### Ligazóns externas 
* Chapter 6: Directed graphs