1. ¿Qué vamos a aprender?
Representan objetos, personas, lugares, equipos o puntos de una situación.
Representan relaciones o conexiones entre dos vértices.
Para cada vértice se anotan los vértices que están conectados directamente con él.
Es la cantidad de aristas incidentes en un vértice.
2. ¿Cuándo conviene usar una matriz de adyacencia?
La matriz de adyacencia es especialmente útil cuando necesitamos trabajar con un grafo de manera organizada, comparar rápidamente muchas parejas de vértices o procesar el grafo mediante un programa o algoritmo.
Permite saber rápidamente si existe una conexión directa entre dos vértices.
Es cómoda cuando podemos organizar todos los vértices en filas y columnas.
Los computadores pueden consultar la matriz para analizar conexiones y recorridos.
En un grafo simple no dirigido, la suma de los valores de una fila corresponde al grado de ese vértice.
3. Ejemplo resuelto: transporte entre cuatro lugares
Supongamos cuatro lugares de una ciudad: A (Colegio), B (Biblioteca), C (Parque) y D (Terminal). Una conexión significa que existe una ruta directa entre dos lugares.
V = {A, B, C, D}
E = {{A,B}, {A,C}, {B,C}, {B,D}}
A: B, C
B: A, C, D
C: A, B
D: B
deg(A)=2
deg(B)=3
deg(C)=2
deg(D)=1
Matriz de adyacencia del ejemplo
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 1 |
| C | 1 | 1 | 0 | 0 |
| D | 0 | 1 | 0 | 0 |
4. Cinco casos prácticos para resolver
En cada situación el estudiante debe construir: 1) lista de vértices, 2) lista de aristas, 3) lista de adyacencias y 4) lista de grados de cada vértice. Después puede construir la matriz de adyacencia si el docente lo solicita.
Caso 1 — El colegio
Un colegio tiene cinco espacios: Entrada (E), Biblioteca (B), Laboratorio (L), Patio (P) y Salón de tecnología (T). Se consideran conexiones directas entre espacios cuando existe un recorrido habitual entre ellos.
Conexiones: E-B, E-P, B-L, B-T, L-T, P-T.
Caso 2 — Transporte urbano
Considera cinco puntos de una ruta urbana: Portal (P), Centro (C), Museo (M), Universidad (U) y Terminal (T). Una arista representa una conexión directa entre dos puntos.
Conexiones: P-C, P-U, C-M, C-U, M-T, U-T.
Caso 3 — Red de amistades
En un grupo se estudian las amistades directas entre Ana (A), Beto (B), Carla (C), Diana (D), Elena (E) y Felipe (F). Una arista significa que dos estudiantes tienen una amistad directa.
Relaciones: A-B, A-C, A-D, B-E, C-E, D-F, E-F.
Caso 4 — Red de Internet
Una pequeña red contiene Router (R), PC1, PC2, Servidor (S) e Impresora (I). Una arista representa una conexión directa entre dos dispositivos.
Conexiones: R-PC1, R-PC2, R-S, PC1-I, PC2-S.
Caso 5 — Entrega de mensajería
Una empresa de mensajería trabaja con cinco puntos: Centro de distribución (C), Zona Norte (N), Zona Centro (Z), Zona Sur (S) y Zona Occidente (O). Una arista representa una conexión directa utilizada para distribuir paquetes entre dos puntos.
Conexiones: C-N, C-Z, C-S, C-O, N-Z, S-O.
5. ¿Cuál representación conviene usar?
| Representación | ¿Para qué sirve? | Pregunta que ayuda a responder |
|---|---|---|
| Grafo dibujado | Observar visualmente la estructura. | ¿Cómo están conectados los elementos? |
| Lista de vértices | Identificar todos los objetos. | ¿Qué elementos participan? |
| Lista de aristas | Enumerar todas las conexiones. | ¿Qué parejas están conectadas? |
| Lista de adyacencias | Ver las conexiones de cada vértice. | ¿Con quién está conectado cada elemento? |
| Lista de grados | Medir cuántas conexiones tiene cada vértice. | ¿Cuál tiene más o menos conexiones? |
| Matriz de adyacencia | Representar todas las parejas en una tabla numérica y facilitar el procesamiento computacional. | ¿Existe conexión directa entre X e Y? |
6. Actividad de cierre
- Escoge uno de los cinco casos.
- Escribe el conjunto de vértices V.
- Escribe el conjunto de aristas E.
- Construye la lista de adyacencias.
- Calcula el grado de cada vértice.
- Identifica el vértice de mayor grado y explica su significado en el problema.
- Construye la matriz de adyacencia.
- Comprueba que la matriz es simétrica y que la suma de cada fila coincide con el grado correspondiente.