Dígrafos

Un dígrafo $G = (V, X)$ es un par de conjuntos $V$ y $X$ donde $V$ es el conjunto de puntos, nodos o vértices y $X$ es un subconjunto del conjunto de los pares ordenados de elementos distintos de $V$ . A los elementos de $X$ los llamaremos arcos.

Dado un arco $e = (u, w)$ llamaremos al primer elemento, $u$ , la cola de $e$ y al segundo elemento, $w$ , la cabeza de $e$ .

El grado de entrada $d_{i n} (v)$ de un vértice $v$ de un dígrafo es la cantidad de arcos que llegan a $v$ . Es decir, la cantidad de arcos que tienen a $v$ como cabeza. El grado de salida $d_{o u t} (v)$ de un vértice $v$ de un dígrafo es la cantidad de arcos que salen de $v$ . Es decir, la cantidad de arcos que tienen a $v$ como cola.

El grafo subyacente de un dígrafo $G$ es el grafo $G^{S}$ que resulta de remover las direcciones de sus arcos (si para un par de vértices hay arcos en ambas direcciones, sólo se coloca una arista entre ellos).

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))

id1 --> id2
id2 --> id3
id3 --> id4
id4 --> id3
id4 --> id1
id1 --> id3
id2 --> id4

El grafo subyacente del mostrado en el dibujo seria el siguiente:

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))

id1 --- id2
id2 --- id3
id3 --- id4
id4 --- id1
id1 --- id3
id2 --- id4

Dado un dígrafo $D$ , el dígrafo traspuesto de $D$ , $D^{t} = (V^{t}, X^{t})$ , es el dígrafo que se obtiene al invertir todas las direcciones de cada arista. Es decir, para todo $(v, u) \in X$ , se tiene que $(u, v) \in X^{t}$ .

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))

id2 --> id1
id3 --> id2
id4 --> id3
id3 --> id4
id1 --> id4
id3 --> id1
id4 --> id2

En el dibujo se puede ver el dígrafo traspuesto del dígrafo dibujado antes.

Moverse por el grafo

Llamamos recorrido o camino orientado en un dígrafo a una sucesión de arcos $e_{1}, e_{2}, \dots, e_{k}$ tal que el primer elemento del arco $e_{i}$ coincide con el segundo de $e_{i - 1}$ , y el segundo elemento de $e_{i}$ con el primero de $e_{i + 1}$ , para todo $2 \leq i \leq k - 1$ .

Un circuito o ciclo orientado en un grafo dirigido es un recorrido orientado que comienza y termina en el mismo vértice.

Un dígrafo se dice fuertemente conexo si para todo par de vértices $u$ , $v$ existen caminos orientados de $u$ a $v$ y de $v$ a $u$ .

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))
id6((6))
id7((7))

id1 --> id2
id2 --> id1
id2 --> id6
id2 --> id4
id3 --> id2
id3 --> id4
id4 --> id5
id4 --> id7
id5 --> id3
id6 --> id3
id7 --> id1
id7 --> id4

En el dibujo de arriba se puede ver un dígrafo fuertemente conexo. También podríamos decir, por mencionar algunos ejemplos, que:

\begin{aligned} P_{1} & = v_{1}, v_{2}, v_{4}, v_{5}, v_{3} & es camino orientado \\ P_{2} & = v_{2}, v_{3}, v_{4} & no es camino orientado \\ C_{1} & = v_{1}, v_{2}, v_{4}, v_{7}, v_{1} & es ciclo orientado \\ C_{2} & = v_{2}, v_{1}, v_{7}, v_{2} & no es ciclo orientado \end{aligned}