12.2: Dígrafos

En esta sección, presentamos otra variante útil de una gráfica. En una gráfica, la existencia de un borde se\(xy\) puede utilizar para modelar una conexión entre\(x\) y\(y\) que va en ambos sentidos. Sin embargo, a veces tal modelo es insuficiente. Por ejemplo, quizás sea posible volar desde Atlanta directamente a Fargo pero no es posible volar desde Fargo directamente a Atlanta. En una gráfica que representa la red aérea, una ventaja entre Atlanta y Fargo perdería la información de que los vuelos solo operan en una dirección. Para hacer frente a este problema, introducimos una nueva estructura discreta. Un dígrafo\(G\) es un par\((V,E)\) donde\(V\) se encuentra un conjunto de vértices y\(E⊂V \times V\) con\(x \neq y\) para cada\((x,y) \in E\). Consideramos el par\((x,y)\) como un borde dirigido de\(x\) a\(y\). Tenga en cuenta que para los vértices distintos\(x\) y\(y\) de\(V\), los pares ordenados\((x,y)\) y\((y,x)\) son distintos, por lo que el dígrafo puede tener uno, ambos o ninguno de los bordes dirigidos\((x,y)\) y\((y,x)\). Esto contrasta con las gráficas, donde los bordes son conjuntos, así\(\{x,y\}\) y\(\{y,x\}\) son los mismos.

Los diagramas de dígrafos utilizan puntas de flecha en los bordes para indicar la dirección. Esto se ilustra en la Figura 12.12. Por ejemplo, el dígrafo allí ilustrado contiene el borde\((a,f)\) pero no el borde\((f,a)\). Contiene ambos bordes\((c,d)\) y\((d,c)\), sin embargo.

Figura 12.12. Un dígrafo

Cuando\(\textbf{G}\) es un dígrafo, una secuencia\(P=(r=u_0,u_1,…,u_t=x)\) de vértices distintos se llama ruta dirigida desde\(r\) hasta\(x\) cuándo\((u_iu_{i+1})\) es un borde dirigido\(\textbf{G}\) para cada\(i=0,1,…,t−1\). Una ruta dirigida\(C=(r=u_0,u_1,…,u_t=x)\) se llama ciclo dirigido cuando\((u_t,u_0)\) es un borde dirigido de\(\textbf{G}\).