Aprende a representar relaciones que tienen un sentido: rutas, mensajes, tareas o enlaces entre páginas web.
Nivel básico · Secundaria
1. ¿Qué es un grafo dirigido o digrafo?
Un grafo dirigido, también llamado digrafo, es un dibujo que representa elementos y relaciones que van en una dirección determinada.
Vértices
Son los puntos o nodos. Representan lugares, personas, páginas o actividades. Se nombran con letras: A, B, C, D, E…
Arcos o aristas dirigidas
Son flechas que conectan dos vértices. La punta indica hacia dónde va la relación.
Dirección
Si hay una flecha de A hacia B, se escribe A → B. Esto no significa que exista una flecha de B hacia A.
Idea clave: en un digrafo, A → B y B → A son dos relaciones diferentes.
2. Fundamentos teóricos
Notación sencilla: usaremos texto simple para nombrar conjuntos. Por ejemplo, escribiremos V = A, B, C para indicar los vértices y A = A→B, B→C para indicar los arcos.
Vértices (V): los nodos del grafo. Ejemplo: V = A, B, C, D, E.
Arcos (A): las flechas dirigidas. Ejemplo: A = A→B, B→C.
Arco de salida: sale de un vértice. En A→B, el arco sale de A.
Arco de entrada: llega a un vértice. En A→B, el arco entra en B.
Camino: sucesión de arcos que permite ir de un vértice a otro siguiendo las flechas.
Lazo: flecha que sale de un vértice y regresa al mismo vértice (A→A).
2.1 Adyacencia e incidencia
➡️ Adyacencia desde
Los vértices a los que llega una flecha que sale de él. Son sus vecinos salientes.
Ejemplo: si A→B y A→C, entonces desde A son B y C.
⬅️ Adyacencia hacia
Los vértices desde los que sale una flecha que llega a él. Son sus vecinos entrantes.
Ejemplo: si A→C y B→C, entonces hacia C son A y B.
🔗 Incidencia
Un arco incide en un vértice cuando una de sus puntas llega a ese vértice. En un digrafo, el arco incide en el vértice de llegada (destino).
Ejemplo: el arco A→B incide en B.
2.2 ¿Qué es la matriz de adyacencia?
Es una tabla cuadrada que representa el digrafo con números 0 y 1.
Escribe los vértices en filas y columnas, en el mismo orden.
En la fila del vértice de salida y la columna del vértice de llegada, escribe 1 si existe la flecha.
Escribe 0 si no existe.
Atención: las filas indican desde dónde sale la flecha; las columnas indican a dónde llega.
Si los vértices están ordenados A, B, C y las flechas son A→B y B→C, la matriz es:
Desde ↓ / Hacia →
A
B
C
A
0
1
0
B
0
0
1
C
0
0
0
La matriz no tiene que ser simétrica: puede haber 1 en A–B y 0 en B–A.
3. Cinco ejemplos resueltos
En cada ejemplo observarás: el digrafo dibujado en canvas, la lista de vértices y arcos, las tablas de adyacencia desde, adyacencia hacia e incidencia, y su matriz de adyacencia.
Ejemplo 1
Cadena de una ruta entre cinco lugares
Un estudiante camina de la casa (A) al parque (B), del parque a la biblioteca (C), de la biblioteca al café (D) y del café a la escuela (E).
Vértices (V): A, B, C, D, E.
Arcos (A): A→B, B→C, C→D, D→E.
Adyacencia e incidencia
Vértice
Adyacencia desde
Adyacencia hacia
Arcos incidentes (que llegan)
A
B
—
—
B
C
A
A→B
C
D
B
B→C
D
E
C
C→D
E
—
D
D→E
Matriz de adyacencia (orden A, B, C, D, E)
Desde / Hacia
A
B
C
D
E
A
0
1
0
0
0
B
0
0
1
0
0
C
0
0
0
1
0
D
0
0
0
0
1
E
0
0
0
0
0
Interpretación: existe una ruta lineal A→B→C→D→E. No hay flechas de regreso.
Ejemplo 2
Envío de mensajes entre cinco amigos
Lucía (A) envía un mensaje a Mateo (B) y a Sara (C). Mateo escribe también a Sara (B→C) y a Diego (B→D). Sara le escribe a Elena (C→E).
Vértices (V): A, B, C, D, E.
Arcos (A): A→B, A→C, B→C, B→D, C→E.
Adyacencia e incidencia
Vértice
Adyacencia desde
Adyacencia hacia
Arcos incidentes (que llegan)
A
B, C
—
—
B
C, D
A
A→B
C
E
A, B
A→C, B→C
D
—
B
B→D
E
—
C
C→E
Matriz de adyacencia (orden A, B, C, D, E)
Desde / Hacia
A
B
C
D
E
A
0
1
1
0
0
B
0
0
1
1
0
C
0
0
0
0
1
D
0
0
0
0
0
E
0
0
0
0
0
Interpretación: desde A salen dos flechas (a B y C). El vértice C recibe flechas de A y B: su adyacencia hacia es {A, B}.
Ejemplo 3
Ciclo de préstamo de libros entre cinco personas
La biblioteca (A) presta un libro a Camila (B); Camila lo pasa a Diego (C); Diego lo pasa a Elena (D); Elena lo pasa a Fabián (E); y Fabián lo devuelve a la biblioteca (E→A).
Vértices (V): A, B, C, D, E.
Arcos (A): A→B, B→C, C→D, D→E, E→A.
Adyacencia e incidencia
Vértice
Adyacencia desde
Adyacencia hacia
Arcos incidentes (que llegan)
A
B
E
E→A
B
C
A
A→B
C
D
B
B→C
D
E
C
C→D
E
A
D
D→E
Matriz de adyacencia (orden A, B, C, D, E)
Desde / Hacia
A
B
C
D
E
A
0
1
0
0
0
B
0
0
1
0
0
C
0
0
0
1
0
D
0
0
0
0
1
E
1
0
0
0
0
Interpretación: las flechas forman un recorrido cerrado A→B→C→D→E→A. Cada vértice tiene un arco entrante y uno saliente.
Ejemplo 4
Requisitos para realizar un proyecto
Primero se investiga (A). Después se puede elaborar una maqueta (B) o preparar una exposición (C). La maqueta y la exposición conducen al ensayo (D). El ensayo conduce a la presentación final (E).
Vértices (V): A, B, C, D, E.
Arcos (A): A→B, A→C, B→D, C→D, D→E.
Adyacencia e incidencia
Vértice
Adyacencia desde
Adyacencia hacia
Arcos incidentes (que llegan)
A
B, C
—
—
B
D
A
A→B
C
D
A
A→C
D
E
B, C
B→D, C→D
E
—
D
D→E
Matriz de adyacencia (orden A, B, C, D, E)
Desde / Hacia
A
B
C
D
E
A
0
1
1
0
0
B
0
0
0
1
0
C
0
0
0
1
0
D
0
0
0
0
1
E
0
0
0
0
0
Interpretación: D recibe arcos de B y de C: dos arcos inciden en D. E no tiene arcos de salida.
Ejemplo 5
Enlaces entre cinco páginas web
La página principal (A) enlaza a Blog (B). Blog enlaza a Noticias (C). Noticias enlaza a Deportes (D). Deportes enlaza a Contacto (E). Contacto enlaza de vuelta a la página principal (E→A). Además, la página principal enlaza directamente a Noticias (A→C).
Vértices (V): A, B, C, D, E.
Arcos (A): A→B, B→C, C→D, D→E, E→A, A→C.
Adyacencia e incidencia
Vértice
Adyacencia desde
Adyacencia hacia
Arcos incidentes (que llegan)
A
B, C
E
E→A
B
C
A
A→B
C
D
A, B
A→C, B→C
D
E
C
C→D
E
A
D
D→E
Matriz de adyacencia (orden A, B, C, D, E)
Desde / Hacia
A
B
C
D
E
A
0
1
1
0
0
B
0
0
1
0
0
C
0
0
0
1
0
D
0
0
0
0
1
E
1
0
0
0
0
Interpretación: el vértice C es muy visitado: recibe flechas de A y B (dos arcos inciden en C) y a su vez envía una flecha a D.
4. Evaluación: construye el digrafo y su matriz
Instrucciones: para cada situación, identifica los vértices y los arcos, dibuja el digrafo con sus flechas, completa la tabla de adyacencia desde / hacia / incidencia y la matriz de adyacencia. No escribas 1 por un camino indirecto: solo por una flecha directa.
Ejercicio 1 · 5 vértices
Recorrido de un paquete por cinco puntos
Un paquete sale del almacén (A) al centro de distribución (B), de B a la bodega regional (C), de C al transportador (D) y de D a la casa del cliente (E).
a. Escribe los arcos:
b. Dibuja el digrafo en el canvas (o en tu cuaderno).
c. Completa la tabla de adyacencia e incidencia.
Vértice
Adyacencia desde
Adyacencia hacia
Arcos incidentes
A
B
C
D
E
d. Completa la matriz. Orden: A, B, C, D, E.
Desde / Hacia
A
B
C
D
E
A
B
C
D
E
Ejercicio 2 · 5 vértices
Actividades de un proyecto escolar
El grupo primero investiga (A). Después puede elaborar una maqueta (B) o preparar una exposición (C). La maqueta conduce al ensayo (D) y la exposición también conduce al ensayo (C→D). El ensayo conduce a la presentación final (E).
a. Escribe todos los arcos:
b. Dibuja el digrafo.
c. Completa la tabla de adyacencia e incidencia.
Vértice
Adyacencia desde
Adyacencia hacia
Arcos incidentes
A
B
C
D
E
d. Completa la matriz. Orden: A, B, C, D, E.
Desde / Hacia
A
B
C
D
E
A
B
C
D
E
Ejercicio 3 · 5 vértices
Conexiones entre cinco estaciones
Una ruta de transporte tiene cinco estaciones: A, B, C, D y E. Las flechas son: A→B, B→C, C→D, D→E, E→A y A→C.
a. ¿Cuántos arcos tiene el digrafo?
b. Dibuja las estaciones y todas las flechas.
c. Completa la tabla de adyacencia e incidencia.
Vértice
Adyacencia desde
Adyacencia hacia
Arcos incidentes
A
B
C
D
E
d. Completa la matriz. Orden: A, B, C, D, E.
Desde / Hacia
A
B
C
D
E
A
B
C
D
E
e. Pregunta final: ¿cuál vértice tiene más arcos incidentes (que llegan a él)?
Revisa antes de entregar: ¿cada fila de la matriz corresponde al vértice de salida? ¿Cada columna al vértice de llegada? ¿Escribiste 1 solo cuando existe una flecha directa?
5. Lista de cotejo para el estudiante
☐ Identifiqué correctamente los vértices.
☐ Dibujé las flechas en la dirección indicada.
☐ Distinguí adyacencia desde y adyacencia hacia para cada vértice.
☐ Identifiqué qué arcos inciden en cada vértice (los que llegan a él).
☐ Usé el mismo orden de vértices en filas y columnas.
☐ Escribí 1 para una flecha directa y 0 cuando no existe.
☐ Verifiqué que cada fila de la matriz coincide con las flechas que salen de ese vértice.