Grafos dirigidos

Un grafo dirigido g, también llamado dígrafo o grafo, es lo mismo que un multígrafo, solo que cada arista e de g tiene una dirección asignada o, en otras palabras, arista e esta identificada por un par ordenado (u,v) de nodos de g en vez del par desordenado [u,v].
Suponga que g  es un grafo dirigido con una arista dirigida e=(u,v). Entonces e también  se llama arco. Mas aun, se usa la siguiente terminología:

1)    e empieza en u y termina en v.

2)    u es el origen o punto inicial de e, y v es el destino o punto terminal de e.

3)    u es un predecesor de v  y v es un sucesor o vecino de u.

4)    u es adyacente hacia v y v es adyacente desde u.

El grado de salida de un nodo u de g, escrito gradsal (u), es el numero de aristas que empiezan en u. similarmente, el grado de entrada de u, escrito gradent (u), es el numero de aristas que terminan en u. un nodo u se llama fuente si tiene un grado de sallida positivo y un grado de entrada nulo. Similarmente, u se llama sumidero si tiene un grado de salida nulo y un grado de entrada positivo. las nociones de camino, camino simple y ciclo se aplican en los grafos dirigidos igual que los grafos no dirigidos excepto que la dirección de cada arista de un camino (ciclo) debe coincidir con la dirección del camino (ciclo). se dice que un nodo v es alcanzable desde un nodo u si existe un camino (dirigido) de u a v. un grafo dirijo g se dice que es conexo, o fuertemente conexo, si para cada par u, v de nodos de g existe un camino de u a v y también un camino de v a u. por otro lado, g se dice que es unilateralmente conexo si para cada par u, v de nodos de g hay un camino de u a v o un camino de v a u.