Grafo dirigido

Un grafo dirigido o digrafo es un tipo de grafo en el cual las aristas tienen un sentido definido,¹​ a diferencia del grafo no dirigido, en el cual las aristas son relaciones simétricas y no apuntan en ningún sentido.

A veces un digrafo es denominado digrafo simple para distinguirlo del caso general del multigrafo dirigido, donde los arcos constituyen un multiconjunto, en lugar de un conjunto. En este caso, puede haber más de un arco que una dos vértices en la misma dirección, distinguiéndose entre sí por su identidad, por su tipo (por ejemplo un tipo de arco representa relaciones de amistad mientras que el otro tipo representa mensajes enviados recientemente entre los nodos), o por un atributo como por ejemplo su importancia o peso. A menudo también se considera que en un digrafo simple no están permitidos los bucles.

Definición formal[editar]

Al igual que en el grafo generalizado, el grafo dirigido está definido por un par de conjuntos ${\displaystyle 𝐺=(𝑉,𝐸)}$, donde:

• ${\displaystyle 𝑉\ne \mathrm{\varnothing }}$, un conjunto no vacío de objetos simples llamados vértices o nodos.
• ${\displaystyle 𝐸\subseteq \{(𝑎,𝑏)\in 𝑉\times 𝑉:𝑎\ne 𝑏\}}$ es un conjunto de pares ordenados de elementos de ${\displaystyle 𝑉}$ denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al segundo nodo (b) dentro del par.

Un arco ${\displaystyle 𝑒=(𝑥,𝑦)}$ se considera dirigido desde ${\displaystyle 𝑥}$ hacia ${\displaystyle 𝑦}$. Otra notación válida es . En ambos casos, el vértice ${\displaystyle 𝑥}$ cumple un rol de «emisor» y el vértice ${\displaystyle 𝑦}$ uno de «receptor».²​

Propiedades[editar]

Sea ${\displaystyle 𝑛=|𝑉|}$ el número de nodos de un grafo dirigido, este podrá a lo más tener ${\displaystyle {𝑛}^2}$ aristas, y ${\displaystyle 𝑛(𝑛-1)}$ en caso de que se excluyan los bucles.³​

Conceptos relacionados[editar]

Si existe un camino compuesto de uno o más arcos que una x con y, entonces a y se le denomina sucesor de x, al igual que a x se le denomina predecesor de y. Dada una arista (x,y), el vértice y se denomina también un sucesor directo de x; correspondientemente, se denomina a x un predecesor directo de y.

Al arco ${\displaystyle (𝑦,𝑥)}$ se le denomina arco invertido de ${\displaystyle (𝑥,𝑦)}$.

Un grafo dirigido G es llamado simétrico si, para cualquier arco que pertenece a G, el arco invertido correspondiente también pertenece a G. Un grafo dirigido simétrico y sin bucles es equivalente a un grafo no dirigido; basta con reemplazar cada par de arcos dirigidos por un solo arco no dirigido.