Un grafo dirigido representa una relación como elementos conectados por flechas. Es una forma visual y computacional de modelar dependencias, rutas, transiciones y vínculos entre datos.
Además de pares ordenados y matrices, una relación discreta puede representarse mediante un grafo dirigido. En esta representación, los elementos son nodos y cada par ordenado se dibuja como una flecha.
Esta forma es especialmente útil cuando queremos visualizar caminos, dependencias, transiciones, conexiones entre módulos o relaciones entre entidades.
Un grafo dirigido está formado por nodos y aristas dirigidas. Una arista dirigida es una flecha que va desde un nodo de origen hacia un nodo de destino.
La flecha indica dirección. Que exista A → B no significa que exista B → A.
Si tenemos una relación como conjunto de pares ordenados, cada par se convierte en una flecha del grafo.
El grafo permite observar rápidamente qué elementos tienen conexiones salientes y cuáles reciben conexiones entrantes.
Supongamos que una aplicación tiene módulos que dependen de otros módulos. La relación puede representarse con flechas.
La flecha Interfaz → API indica que el módulo Interfaz depende del módulo API.
Cuando no dibujamos el grafo, podemos representarlo como una lista de adyacencia. En una lista de adyacencia, cada nodo indica a qué nodos apunta.
Esta estructura es muy común en programación porque facilita recorrer las conexiones desde cada nodo.
Podemos representar un grafo dirigido mediante un objeto donde cada clave es un nodo y cada valor es la lista de nodos de destino.
const grafo = {
Interfaz: ["API"],
API: ["BaseDatos"],
Reportes: ["API"],
Tests: ["Interfaz"],
BaseDatos: []
};
console.log(grafo.API);El arreglo asociado con cada nodo contiene sus conexiones salientes.
Si tenemos una relación como lista de pares, podemos construir automáticamente la lista de adyacencia.
const relacion = [
["Interfaz", "API"],
["API", "BaseDatos"],
["Reportes", "API"],
["Tests", "Interfaz"]
];
function crearListaAdyacencia(pares) {
const grafo = {};
for (const [origen, destino] of pares) {
if (!grafo[origen]) grafo[origen] = [];
if (!grafo[destino]) grafo[destino] = [];
grafo[origen].push(destino);
}
return grafo;
}
console.log(crearListaAdyacencia(relacion));Incluimos también los nodos que solo aparecen como destino, para que el grafo quede completo.
En un grafo dirigido, el grado de salida de un nodo es la cantidad de flechas que salen de él. El grado de entrada es la cantidad de flechas que llegan a él.
| Concepto | Pregunta que responde | Ejemplo |
|---|---|---|
| Grado de salida | ¿A cuántos nodos apunta este nodo? | API apunta a BaseDatos: salida 1 |
| Grado de entrada | ¿Cuántos nodos apuntan a este nodo? | API recibe flechas desde Interfaz y Reportes: entrada 2 |
Podemos calcular los grados de entrada y salida a partir de una lista de pares ordenados.
const relacion = [
["Interfaz", "API"],
["API", "BaseDatos"],
["Reportes", "API"],
["Tests", "Interfaz"]
];
const grados = {};
for (const [origen, destino] of relacion) {
if (!grados[origen]) grados[origen] = { entrada: 0, salida: 0 };
if (!grados[destino]) grados[destino] = { entrada: 0, salida: 0 };
grados[origen].salida++;
grados[destino].entrada++;
}
console.log(grados);Un camino es una secuencia de flechas que permite ir desde un nodo hasta otro. Por ejemplo, si existe A → B y B → C, entonces hay un camino de A a C.
Los caminos son importantes para analizar rutas, dependencias indirectas, estados alcanzables y propagación de cambios.
| Representación | Ventaja principal | Uso típico |
|---|---|---|
| Pares ordenados | Enumera vínculos de forma explícita. | Definir relaciones pequeñas. |
| Matriz | Facilita cálculos sistemáticos. | Algoritmos con relaciones finitas. |
| Grafo dirigido | Visualiza conexiones y caminos. | Rutas, redes, dependencias y transiciones. |
La representación mediante grafos dirigidos permite ver una relación como una red de conexiones con dirección. Esta perspectiva es muy útil cuando importa la estructura global de los vínculos, no solo la existencia de pares individuales.
En el próximo tema estudiaremos relaciones reflexivas, simétricas y transitivas, propiedades fundamentales para clasificar relaciones discretas.