Introducción a los grafos
Un grafo es una estructura matemática que modela relaciones entre pares de objetos. Las redes de carreteras, las conexiones sociales, los árboles de dependencias, los circuitos eléctricos e internet son todos grafos. Los algoritmos de grafos resuelven problemas fundamentales sobre estas estructuras: encontrar caminos más cortos, detectar ciclos, conectar redes con coste mínimo y agrupar componentes conexas.
Definición
Un grafo \(G = (V, E)\) consta de:
- \(V\): un conjunto de vértices (también llamados nodos). \(|V| = n\).
- \(E\): un conjunto de aristas (también llamadas arcos o enlaces), cada una conectando un par de vértices. \(|E| = m\).
Una arista entre los vértices \(u\) y \(v\) se escribe \((u,v)\) o \(\{u,v\}\).
El grado de un vértice \(v\), escrito \(\deg(v)\), es el número de aristas incidentes en \(v\). Para grafos dirigidos: grado de entrada (aristas que llegan) y grado de salida (aristas que salen).
Lema del apretón de manos: \(\sum_{v \in V} \deg(v) = 2m\) (cada arista contribuye 2 a la suma total de grados).
Tipos de grafos
Dirigido vs no dirigido
En un grafo no dirigido, las aristas no tienen dirección: \((u,v)\) y \((v,u)\) son la misma arista. Redes de carreteras con calles de doble sentido, redes de amistad.
En un grafo dirigido (dígrafo), cada arista tiene una dirección: \((u,v)\) va de \(u\) a \(v\) pero no necesariamente de \(v\) a \(u\). Enlaces web, redes de citas, grafos de dependencias.
Ponderado vs no ponderado
En un grafo ponderado, cada arista lleva un peso numérico \(w(u,v)\): distancia, coste, capacidad, tiempo. Los grafos no ponderados tratan todas las aristas por igual (o equivalentemente, todos los pesos son 1).
Conexo vs no conexo
Un grafo no dirigido es conexo si existe un camino entre cada par de vértices. Una componente conexa es un subgrafo conexo maximal. Un grafo dirigido es fuertemente conexo si cada vértice es alcanzable desde cualquier otro vértice.
Cíclico vs acíclico
Un ciclo es un camino que comienza y termina en el mismo vértice. Un grafo sin ciclos es acíclico. Un grafo no dirigido acíclico y conexo es un árbol: tiene exactamente \(n-1\) aristas y un único camino entre dos vértices cualesquiera.
Representaciones de grafos
Dos estructuras de datos estándar para almacenar grafos en memoria:
Matriz de adyacencia
Una matriz \(n \times n\) \(A\) donde \(A_{ij} = 1\) (o \(w_{ij}\) para grafos ponderados) si existe una arista de \(i\) a \(j\), y 0 en caso contrario.
Para el grafo no dirigido anterior (A, B, C, D):
\[A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}\]
Ventajas: búsqueda de aristas en \(O(1)\); natural para grafos densos. Desventajas: \(O(n^2)\) de memoria independientemente del número de aristas; ineficiente para grafos dispersos.
Lista de adyacencia
Cada vértice almacena una lista de sus vecinos. Para el mismo grafo:
A: [B, C]
B: [A, C, D]
C: [A, B, D]
D: [B, C]Ventajas: \(O(n + m)\) de memoria; eficiente para grafos dispersos (la mayoría de redes reales). Desventajas: búsqueda de aristas en \(O(\deg(v))\).
| Matriz de adyacencia | Lista de adyacencia | |
|---|---|---|
| Memoria | \(O(n^2)\) | \(O(n + m)\) |
| Búsqueda de arista \((u,v)\) | \(O(1)\) | \(O(\deg(u))\) |
| Iterar vecinos de \(v\) | \(O(n)\) | \(O(\deg(v))\) |
| Mejor para | Grafos densos (\(m \approx n^2\)) | Grafos dispersos (\(m \ll n^2\)) |
La mayoría de grafos del mundo real (redes de carreteras, redes sociales, grafos web) son dispersos: \(m = O(n)\) o \(O(n \log n)\). Las listas de adyacencia son casi siempre la elección correcta.
Caminos, ciclos y conectividad
Un camino de \(u\) a \(v\) es una secuencia de vértices \(u = v_0, v_1, \ldots, v_k = v\) donde cada par consecutivo \((v_i, v_{i+1})\) es una arista. La longitud del camino es el número de aristas (\(k\)) para grafos no ponderados, o la suma de los pesos de las aristas para grafos ponderados.
Un camino simple visita cada vértice como máximo una vez. Un ciclo es un camino donde \(v_0 = v_k\) y se recorre al menos una arista. Un ciclo simple visita cada vértice exactamente una vez (salvo el inicio/fin).
El camino más corto de \(u\) a \(v\) es el camino con peso total mínimo. Encontrar caminos más cortos es uno de los problemas más importantes de la teoría de grafos y el objeto del algoritmo de Dijkstra.
Familias especiales de grafos
Varias familias de grafos aparecen frecuentemente en algoritmos y aplicaciones:
- Árbol: grafo no dirigido acíclico y conexo. \(n\) vértices, \(n-1\) aristas. Camino único entre dos vértices cualesquiera.
- Bosque: grafo no dirigido acíclico (unión de árboles). Sin requisito de camino único.
- DAG (Grafo Dirigido Acíclico): grafo dirigido sin ciclos dirigidos. Se usa para resolución de dependencias, ordenación topológica, programación dinámica.
- Grafo bipartito: los vértices se dividen en dos conjuntos \(U\) y \(V\); todas las aristas van entre \(U\) y \(V\). Modela emparejamientos (trabajos con trabajadores, estudiantes con cursos).
- Grafo completo \(K_n\): cada par de vértices está conectado. \(m = n(n-1)/2\) aristas.
- Grafo planar: puede dibujarse en el plano sin que las aristas se crucen. Las redes de carreteras suelen ser casi planares.
💡 Grafos en R
library(igraph)
# Crear un grafo no dirigido ponderado
g <- graph_from_edgelist(
matrix(c("A","B", "A","C", "B","C", "B","D", "C","D"),
ncol=2, byrow=TRUE),
directed=FALSE
)
E(g)$weight <- c(4, 2, 3, 7, 1)
# Propiedades básicas
vcount(g) # número de vértices
ecount(g) # número de aristas
degree(g) # grado de cada vértice
is_connected(g) # TRUE/FALSE
# Matriz de adyacencia
as_adjacency_matrix(g, attr="weight")
# Camino más corto (usa Dijkstra internamente)
shortest_paths(g, from="A", to="D", weights=E(g)$weight)
distances(g, weights=E(g)$weight) # matriz de distancias completa
# Representación gráfica
plot(g, edge.label=E(g)$weight, vertex.color="#bfdbfe",
edge.color="#64748b", vertex.label.color="#1e293b")
