1. Grafos y combinatoria
Un grafo está formado por vértices y aristas. Los vértices representan objetos o estados, mientras que las aristas representan relaciones, conexiones o movimientos.
La combinatoria permite responder preguntas como cuántos grafos pueden construirse, cuántas conexiones tiene una red o cuántos recorridos cumplen determinadas condiciones.
2. Grafos simples no dirigidos
En un grafo simple no dirigido no hay lazos ni aristas repetidas. Cada par de vértices puede estar conectado o no, por lo que un grafo con n vértices tiene:
C(n, 2) = n(n - 1)/2 pares posibles de vértices.
Como cada par tiene dos opciones, existen 2C(n, 2) grafos distintos sobre esos vértices etiquetados.
3. Grafos dirigidos
En un grafo dirigido, una conexión entre u y v es diferente de una conexión entre v y u. Para n vértices, sin lazos, hay n(n - 1) arcos posibles.
Por lo tanto, la cantidad de grafos dirigidos simples sobre vértices etiquetados es:
2n(n - 1)
4. Grados de los vértices
El grado de un vértice es la cantidad de aristas que inciden en él. En un grafo no dirigido simple, un vértice puede tener grado entre 0 y n - 1.
El lema del apretón de manos establece:
La suma de los grados de todos los vértices es igual a dos veces la cantidad de aristas.
Cada arista contribuye una vez al grado de cada uno de sus dos extremos.
5. Grafos con una cantidad fija de aristas
Si se desea construir un grafo simple con n vértices y exactamente m aristas, hay que elegir m pares entre los C(n, 2) pares disponibles:
C(C(n, 2), m) grafos posibles.
Este conteo supone que los vértices están identificados y que dos grafos difieren si tienen una arista distinta.
6. Vecindades y matrices
La matriz de adyacencia representa un grafo mediante una tabla. En un grafo simple no dirigido es simétrica: si Ai,j = 1, entonces Aj,i = 1.
Para n vértices, la parte superior de la matriz contiene C(n, 2) decisiones independientes.
function aristasPosibles(n) {
return n * (n - 1) / 2;
}
function matrizVacia(n) {
return Array.from({ length: n }, function () {
return Array(n).fill(0);
});
}
console.log(aristasPosibles(5)); // 107. Caminos y recorridos
Un camino es una secuencia de vértices conectados. Contar caminos puede significar contar secuencias de una longitud fija, recorridos entre dos vértices o rutas que no repiten vértices.
Si cada paso ofrece una cantidad constante de opciones y no existen restricciones, puede aparecer un crecimiento exponencial. Las restricciones del grafo reducen las posibilidades.
8. Caminos de longitud fija
En un grafo dirigido, una matriz de adyacencia elevada a la potencia k contiene en la posición (i, j) la cantidad de recorridos de longitud k desde i hasta j.
La multiplicación de matrices combina recorridos parciales: cada término suma las formas de pasar por un vértice intermedio.
9. Árboles
Un árbol es un grafo conexo sin ciclos. Entre dos vértices existe exactamente un camino simple.
Los árboles etiquetados con n vértices se pueden contar mediante la fórmula de Cayley:
nn-2, para n ≥ 2.
Esta fórmula aparece en redes, conexiones mínimas y estructuras jerárquicas.
10. Subgrafos
Un subgrafo se obtiene seleccionando vértices, aristas o ambos. Un grafo con m aristas tiene 2m subconjuntos de aristas posibles.
Cuando se buscan subgrafos que cumplen una propiedad, la tarea consiste en filtrar ese conjunto de posibilidades o diseñar un conteo más específico.
11. Coloraciones
Una coloración asigna colores a los vértices de modo que vértices adyacentes reciban colores diferentes. Si hay k colores y n vértices sin restricciones, existen kn asignaciones.
Las aristas eliminan asignaciones inválidas. El polinomio cromático de un grafo cuenta las coloraciones válidas según el número de colores disponibles.
12. Recubrimientos y emparejamientos
Un emparejamiento es un conjunto de aristas que no comparten extremos. Contar emparejamientos puede modelar asignaciones sin conflictos, parejas de tareas o conexiones simultáneas.
Los recubrimientos de vértices y de aristas también son problemas combinatorios: hay que elegir elementos que cubran las relaciones requeridas.
13. Ejemplo: contar grafos simples
La siguiente función calcula cuántos grafos simples diferentes pueden formarse sobre n vértices etiquetados. Se utiliza la cantidad de pares posibles y una potencia de dos.
function grafosSimples(n) {
const pares = n * (n - 1) / 2;
return Math.pow(2, pares);
}
console.log(grafosSimples(4)); // 6414. Simulación: matriz de adyacencia
Selecciona la cantidad de vértices. La simulación crea una matriz de adyacencia para un grafo simple no dirigido, conectando cada vértice con el siguiente y mostrando los grados.
15. Aplicaciones informáticas
La combinatoria de grafos aparece en redes de comunicación, mapas, dependencias, recomendaciones, planificación, análisis de relaciones, buscadores y diseño de conexiones.
16. Resumen
Los grafos ofrecen un lenguaje para representar relaciones y la combinatoria permite contar sus posibilidades. Se pueden contar grafos, aristas, caminos, árboles, subgrafos, coloraciones y emparejamientos. Estos conteos ayudan a diseñar algoritmos y estimar su complejidad.