14 Grafos dirigidos

Sea $G$ un grafo y $\bar G$ un grafo dirigido (digrafo).

Vocabulario:

fuertemente conexo	$\bar G$ es fuertemente conexo, si existe un recorrido
	entre cada pareja de vértices de $G$
orientable	$G$ es orientable, si existe un grafo $\bar G \simeq G$
	que es fuertemente conexo
componente fuertemente conexa	conjunto máximo de vértices de $\bar G$
	cuyo subgrafo inducido es fuertemente conexo

Notaciones:

$d_i(v)$	grado entrante
$d_o(v)$	grado saliente

Teorema (Robbins):

$G$ orientable $\qquad\Longrightarrow\qquad$ $G$ es conexo y no contiene puentes

¿Algoritmo que calcule una orientación?

(¿Qué se entiende bajo una orientación óptima? Depende: minimizar el promedio de las distancias, minimizar el máximo de las distancias, minimizar el máximo de las diferencias entre las distancias en $G$ y en $\bar G$ correspondientes.)

Se puede explorar también un digrafo en anchura (BFS) o en profundidad (DFS). A parte de las aristas del árbol y las aristas de retroceso, DFS produce aristas de progreso y aristas de cruce.

DFS se usa para producir una ordenación topológica de un digrafo acíclico, es decir, en el orden aparece un vértice $v$ antes de un vértice $w$, si existe un camino desde $v$ a $w$.

DFS se usa para determinar los componentes fuertemente conexos.

¿Algoritmo que calcule los componentes fuertemente conexos?

se puede seguir también recorridos eulerianos:

Teorema:

$\bar G$ es euleriano $\qquad\Longleftrightarrow\qquad$ $\bar G$ es conexo y $\forall v\in V: d_i(v)=d_o(v)$

¿Algoritmo que calcule un camino euleriano en un digrafo?