En un grafo completo, cada vértice está conectado directamente con todos los demás. Esta conectividad máxima permite estudiar combinaciones, redes densas y el crecimiento del número de relaciones.
Un grafo puede tener pocas conexiones o ser muy denso. El caso extremo ocurre cuando todos los pares de vértices diferentes están unidos por una arista.
Esta estructura recibe el nombre de grafo completo. Aunque su definición es sencilla, resulta útil para comprender cuántas relaciones pueden existir como máximo y cómo crece su cantidad cuando agregamos vértices.
Un grafo simple no dirigido es completo cuando cada par de vértices distintos es adyacente.
No faltan conexiones posibles, no hay aristas repetidas y ningún vértice posee un bucle.
El grafo completo con n vértices se representa mediante la notación Kn. La letra K proviene del término alemán komplett.
| Grafo | Vértices | Aristas | Forma habitual |
|---|---|---|---|
| K1 | 1 | 0 | Un punto |
| K2 | 2 | 1 | Un segmento |
| K3 | 3 | 3 | Un triángulo |
| K4 | 4 | 6 | Cuatro nodos totalmente conectados |
| K5 | 5 | 10 | Cinco nodos totalmente conectados |
Cada vértice puede conectarse con los otros n − 1 vértices. Si multiplicamos n(n − 1), contamos cada arista dos veces: una desde cada extremo. Por eso dividimos entre dos.
Por ejemplo, K6 posee 6 × 5 / 2 = 15 aristas.
Mueve el selector para cambiar la cantidad de vértices. La aplicación genera todas las conexiones posibles. Pulsa un nodo para resaltar sus aristas y comprobar su grado.
Observa que agregar un vértice a Kn exige conectarlo con los n vértices anteriores. Por eso el número de aristas crece mucho más rápido que el de nodos.
En Kn, cada vértice está conectado con todos los demás. Por lo tanto, todos poseen el mismo grado.
K8, por ejemplo, tiene ocho vértices de grado 7. Un grafo cuyos vértices tienen el mismo grado se denomina regular; Kn es regular de grado n − 1.
La cantidad de aristas crece de manera cuadrática. Duplicar la cantidad de vértices produce aproximadamente cuatro veces más conexiones.
| Vértices | Aristas máximas | Nuevas aristas al agregar un vértice |
|---|---|---|
| 5 | 10 | 4 respecto de K₄ |
| 10 | 45 | 9 respecto de K₉ |
| 100 | 4950 | 99 respecto de K₉₉ |
| 1000 | 499500 | 999 respecto de K₉₉₉ |
La expresión Kn normalmente se refiere a un grafo simple no dirigido. En un grafo dirigido completamente conectado puede existir un arco desde cada vértice hacia todos los demás.
No se divide entre dos porque (A, B) y (B, A) son arcos diferentes.
Para generar todas las aristas, recorremos cada par una sola vez. El segundo índice comienza después del primero para evitar bucles y duplicados.
function grafoCompleto(n) {
const vertices = Array.from({ length: n }, (_, i) => i);
const aristas = [];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
aristas.push([i, j]);
}
}
return { vertices, aristas };
}
const k5 = grafoCompleto(5);
console.log(k5.aristas);
console.log("Cantidad:", k5.aristas.length);En un grafo simple podemos comparar la cantidad de aristas existentes con la cantidad máxima posible.
function esCompleto(cantidadVertices, cantidadAristas) {
const maximo = cantidadVertices * (cantidadVertices - 1) / 2;
return cantidadAristas === maximo;
}
console.log(esCompleto(4, 6));
console.log(esCompleto(4, 5));Esta comprobación presupone que el grafo es simple. Si la estructura permite duplicados, primero debemos verificar que cada par diferente aparezca una sola vez.
| Situación | Uso de un grafo completo | Consideración |
|---|---|---|
| Comparar todos los pares | Cada objeto se relaciona con los demás | Costo cuadrático |
| Red de comunicación | Conexión directa entre equipos | Difícil de escalar |
| Torneo todos contra todos | Cada participante enfrenta a los demás | Una arista por encuentro |
| Problema del viajante | Todos los destinos pueden conectarse | Se agregan pesos a las aristas |
La conectividad completa ofrece rutas directas, pero requiere almacenar y procesar muchas aristas cuando n crece.
Los grafos completos representan la conectividad máxima dentro de un grafo simple. Sirven para analizar todos los pares posibles, pero su rápido crecimiento obliga a considerar cuidadosamente el costo de almacenamiento y procesamiento.
En el próximo tema estudiaremos los grafos bipartitos, cuyos vértices se dividen en dos conjuntos y solo se conectan entre conjuntos diferentes.