La teoría de grafos modela objetos y las conexiones entre ellos. Con vértices y aristas podemos representar redes, rutas, dependencias, relaciones sociales, enlaces web y estructuras de datos.
Muchos problemas no consisten en procesar elementos aislados, sino en estudiar cómo se conectan. Una ciudad se relaciona con otras por rutas, una tarea depende de otras tareas y una cuenta sigue a otras cuentas.
Un grafo es una abstracción que conserva precisamente esa información de conexión. La posición o el dibujo de sus puntos no es lo esencial: importa qué vértices están relacionados por aristas.
Un grafo no dirigido se expresa como G = (V, E), donde V es un conjunto de vértices y E es un conjunto de aristas. Cada arista une dos vértices.
En un grafo no dirigido, {A, B} y {B, A} representan la misma arista. El par no tiene dirección; solo expresa que A y B son adyacentes.
Los vértices, también llamados nodos, representan las entidades del problema. Las aristas representan la relación o conexión definida por el modelo.
El significado de una arista debe declararse. La misma colección de entidades puede producir grafos distintos según se modele amistad, seguimiento, distancia, comunicación o dependencia.
El orden de un grafo es la cantidad de vértices, |V|. El tamaño es la cantidad de aristas, |E|.
Estas cantidades permiten comparar grafos y estimar el costo de sus algoritmos. En programación es común usar V para el número de vértices y E para el número de aristas.
Dos vértices son adyacentes si una arista los une. Una arista es incidente con los vértices que conecta.
La adyacencia es una relación simétrica en grafos no dirigidos. En grafos dirigidos se reemplaza por relaciones de entrada y salida, que no tienen por qué ser recíprocas.
Un grafo simple no tiene lazos ni aristas paralelas. Un lazo conecta un vértice consigo mismo; aristas paralelas son varias aristas que unen el mismo par de vértices.
Si se permiten aristas paralelas se habla de multigrafo. Puede ser apropiado para modelar, por ejemplo, varias rutas o vuelos diferentes entre las mismas ciudades.
El grado de un vértice v, escrito deg(v), es la cantidad de aristas incidentes en v. En un grafo simple sin lazos coincide con la cantidad de vecinos de v.
Un vértice de grado 0 se llama aislado. Un vértice de grado 1 se llama hoja o vértice pendiente en muchos contextos.
En todo grafo no dirigido finito, la suma de los grados de los vértices es igual al doble de la cantidad de aristas:
Cada arista contribuye uno al grado de cada uno de sus dos extremos, por eso se cuenta dos veces. Una consecuencia es que la cantidad de vértices de grado impar siempre es par.
Un grafo simple no dirigido de n vértices tiene como máximo una arista por cada par no ordenado de vértices. Por lo tanto, el máximo es:
El grafo que contiene todas esas aristas se llama grafo completo y se denota Kn. En él, cada vértice tiene grado n - 1.
En un grafo dirigido o digrafo, las aristas tienen orientación y se representan como pares ordenados (u, v). La arista indica una conexión que va de u hacia v.
Los enlaces web, los seguidores de una red social y las dependencias de tareas se modelan a menudo con grafos dirigidos porque la relación no es necesariamente simétrica.
En un digrafo, el grado de salida de v es el número de aristas que salen de v; el grado de entrada es el número de aristas que llegan a v.
La suma de todos los grados de salida es igual al número de aristas, y lo mismo ocurre con la suma de grados de entrada. Cada arista aporta una salida y una entrada.
Un grafo ponderado asigna un peso a cada arista. El peso puede representar distancia, tiempo, costo, capacidad, prioridad o cualquier medida definida por el problema.
Los algoritmos de caminos mínimos y redes de costo usan pesos. Debe especificarse si un peso mayor es mejor, peor o simplemente una magnitud neutra para interpretar correctamente el resultado.
Una lista de adyacencia guarda, para cada vértice, sus vecinos. Es una representación eficiente para grafos dispersos, es decir, con muchas menos aristas que el máximo posible.
Recorrer los vecinos de un vértice es directo. La memoria utilizada es O(V + E), por lo que esta estructura es frecuente en implementaciones de algoritmos sobre grafos.
Una matriz de adyacencia usa una tabla V × V. La celda (i, j) vale 1 si existe una arista de i a j, y 0 en caso contrario; en grafos ponderados puede contener el peso.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 0 |
| D | 0 | 1 | 0 | 0 |
La matriz de un grafo no dirigido es simétrica respecto de la diagonal. Consultar si existe una arista es O(1), pero guardar la matriz ocupa O(V²), incluso cuando hay pocas conexiones.
| Operación | Lista de adyacencia | Matriz de adyacencia |
|---|---|---|
| Memoria | O(V + E) | O(V²) |
| Consultar si u-v existe | depende del grado de u | O(1) |
| Recorrer vecinos de u | O(grado(u)) | O(V) |
| Mejor escenario | grafo disperso | grafo denso o muchas consultas de arista |
La elección depende del algoritmo y de la densidad del grafo. No hay una representación universalmente mejor.
class GrafoNoDirigido {
constructor() {
this.adyacentes = new Map();
}
agregarVertice(vertice) {
if (!this.adyacentes.has(vertice)) this.adyacentes.set(vertice, new Set());
}
agregarArista(origen, destino) {
if (origen === destino) throw new Error("no se permiten lazos en este grafo simple");
this.agregarVertice(origen);
this.agregarVertice(destino);
this.adyacentes.get(origen).add(destino);
this.adyacentes.get(destino).add(origen);
}
vecinos(vertice) {
return [...(this.adyacentes.get(vertice) ?? [])];
}
}
const grafo = new GrafoNoDirigido();
grafo.agregarArista("A", "B");
grafo.agregarArista("A", "C");
console.log(grafo.vecinos("A")); // ["B", "C"]Los Set evitan aristas paralelas y la inserción en ambos sentidos mantiene la simetría. Si el dominio necesita lazos o múltiples conexiones, debe usarse otra representación.
class GrafoDirigido {
constructor() {
this.salientes = new Map();
}
agregarArista(origen, destino) {
if (!this.salientes.has(origen)) this.salientes.set(origen, new Set());
if (!this.salientes.has(destino)) this.salientes.set(destino, new Set());
this.salientes.get(origen).add(destino);
}
vecinosSalientes(vertice) {
return [...(this.salientes.get(vertice) ?? [])];
}
}
const red = new GrafoDirigido();
red.agregarArista("Ana", "Beto");
red.agregarArista("Beto", "Carla");
console.log(red.vecinosSalientes("Ana")); // ["Beto"]Agregar (A, B) no agrega automáticamente (B, A). Para responder consultas sobre vecinos entrantes de forma eficiente conviene mantener también una estructura de adyacencia inversa.
Un subgrafo usa un subconjunto de vértices y aristas de un grafo original. Un subgrafo inducido por un conjunto de vértices conserva todas las aristas del grafo original cuyos extremos pertenecen a ese conjunto.
Los subgrafos permiten enfocarse en una parte de una red: usuarios de una comunidad, servidores de una región o módulos de un proyecto.
Un grafo es bipartito si sus vértices pueden separarse en dos conjuntos disjuntos U y W, y todas las aristas van de un conjunto al otro. No hay aristas dentro del mismo grupo.
Los grafos bipartitos modelan relaciones entre dos tipos de entidades. Más adelante aparecen en problemas de asignación y emparejamiento.
Un dibujo de un grafo puede cambiar la posición de los vértices, la longitud de las aristas o el cruce visual de líneas sin cambiar el grafo. Dos aristas que se cruzan en el papel no crean un vértice nuevo salvo que se declare explícitamente.
Esta distinción evita errores al interpretar mapas esquemáticos, diagramas de redes y diagramas de Hasse.
La calidad del resultado depende de que los vértices, las aristas, las direcciones y los pesos representen adecuadamente el problema real.
La teoría de grafos ofrece un lenguaje compacto para describir conexiones. En el próximo tema estudiaremos árboles, una familia especial de grafos que organiza datos de manera jerárquica.