La teoría de grafos usa conjuntos para representar vértices, aristas, relaciones, caminos, vecindades y conexiones entre objetos.
Un grafo es una estructura matemática que permite representar objetos y conexiones entre ellos. La teoría de conjuntos aparece desde su definición más básica.
Los objetos se agrupan en un conjunto de vértices y las conexiones se describen mediante un conjunto de aristas.
Un grafo suele escribirse como:
Donde V es el conjunto de vértices y E es el conjunto de aristas.
Cada vértice es un elemento del conjunto V. Si una ciudad forma parte de una red de rutas, puede representarse como un vértice.
La pertenencia permite saber si un objeto pertenece al grafo.
Una arista conecta dos vértices. En un grafo no dirigido, una arista puede representarse como un conjunto de dos elementos.
Esto indica que existe una conexión entre A y B, sin importar el sentido.
En un grafo dirigido, las aristas tienen orientación. Por eso se representan mediante pares ordenados.
La arista (A, B) no significa lo mismo que (B, A).
En un grafo dirigido, el conjunto de aristas es un subconjunto del producto cartesiano de vértices consigo mismo.
Cada arista dirigida es un par ordenado formado por dos vértices.
Un grafo dirigido puede verse como una relación definida sobre un conjunto de vértices.
Si (A, B) ∈ R, entonces hay una conexión dirigida desde A hacia B.
La vecindad de un vértice es el conjunto de vértices conectados con él.
Esto indica que B y C son vecinos de A.
El grado de un vértice en un grafo no dirigido es la cantidad de aristas incidentes en él. También puede verse como la cardinalidad de su vecindad cuando no hay lazos ni aristas múltiples.
Si N(A) = {B, C, D}, entonces grado(A) = 3.
Un camino es una sucesión de vértices donde cada par consecutivo está conectado por una arista.
Para validar un camino se verifica que cada conexión pertenezca al conjunto de aristas.
Un ciclo es un camino que comienza y termina en el mismo vértice, sin repetir vértices intermedios en su forma simple.
Los ciclos son importantes para analizar dependencias, rutas cerradas y estructuras recurrentes.
Un grafo es conexo si para cualquier par de vértices existe al menos un camino que los une.
La conectividad puede estudiarse usando conjuntos de vértices alcanzables.
Una componente conexa es un subconjunto maximal de vértices donde todos están conectados entre sí mediante caminos.
Las componentes separan el grafo en regiones independientes.
Un subgrafo se forma tomando subconjuntos de vértices y aristas de un grafo original.
Los subgrafos permiten estudiar partes específicas de una red.
Si dos grafos comparten el mismo tipo de elementos, se pueden combinar mediante operaciones de conjuntos.
| Operación | Vértices | Aristas |
|---|---|---|
| Unión | V₁ ∪ V₂ | E₁ ∪ E₂ |
| Intersección | V₁ ∩ V₂ | E₁ ∩ E₂ |
| Diferencia | V₁ - V₂ | E₁ - E₂ |
Una forma común de representar grafos en programación es asociar cada vértice con el conjunto de sus vecinos.
Esta representación es eficiente para consultar vecindades y recorrer conexiones.
En JavaScript se puede representar una lista de adyacencia usando Map y Set.
const grafo = new Map([
["A", new Set(["B", "C"])],
["B", new Set(["A", "D"])],
["C", new Set(["A"])],
["D", new Set(["B"])]
]);
console.log(grafo.get("A")); // Set { "B", "C" }Cada clave del mapa representa un vértice, y cada conjunto almacena sus vecinos.
Para saber si existe una conexión entre dos vértices, se consulta la pertenencia dentro del conjunto de vecinos.
const grafo = new Map([
["A", new Set(["B", "C"])],
["B", new Set(["A", "D"])],
["C", new Set(["A"])],
["D", new Set(["B"])]
]);
function existeArista(grafo, origen, destino) {
return grafo.has(origen) && grafo.get(origen).has(destino);
}
console.log(existeArista(grafo, "A", "C")); // true
console.log(existeArista(grafo, "C", "D")); // falseLa operación central es una pregunta de pertenencia: destino ∈ N(origen).
Los grafos aparecen en muchos problemas reales donde existen entidades conectadas.
La teoría de grafos se apoya directamente en la teoría de conjuntos. Un grafo se define mediante conjuntos de vértices y aristas, y sus propiedades se estudian con pertenencia, subconjuntos, relaciones, producto cartesiano, cardinalidad y operaciones entre conjuntos.
Comprender esta base permite modelar redes, rutas, dependencias y conexiones con mayor precisión.