Los grafos completos
--------------------
En combinatoria, un
grafo es un conjunto de puntos (los
vértices), algunos de los cuales están unidos entre sí por líneas (las
aristas). La forma geométrica de las líneas no importa; lo único que cuenta son los vértices que estas permiten unir (véase
les Graphes,
Bibliothèque Tangente 54, 2015).
Un grafo se dice completo cuando cada uno de sus vértices está unido a todos los demás. El grafo completo con n vértices se denota por Kn.
[/encadre]
Primeros esbozos
-------------------
El grafo completo con dos vértices, denotado por K2, no presenta ninguna dificultad: basta con trazar un segmento entre dos puntos. El caso de K3 no es más difícil: basta con dibujar un triángulo; cada cual elegirá el que le parezca más estético… Con cuatro vértices, empieza a surgir la cuestión de los cruces. La representación más habitual es la siguiente, en la que aparece un cruce.
Sin embargo, si se disponen los puntos de otro modo o se trazan aristas «menos rígidas», se pueden evitar los cruces. Por tanto, el número mínimo de cruces de K4 es, de hecho, cero. Se escribe: cr (K4) = 0.
Pasemos al caso del grafo completo con cinco vértices. Tras algunos intentos, parece inevitable que las aristas se crucen al menos una vez… Pero ¿estamos seguros?
Es posible demostrar que cr (K5) = 1, es decir, que toda representación de K5 en el plano requiere al menos un cruce. De hecho, utilizando hábilmente algunos resultados fundamentales de teoría de grafos, se puede ir aún más lejos. Situémonos en el caso general del grafo completo Kn. Cada uno de sus vértices está unido a los otros n – 1, y cada arista une dos vértices. Por tanto, este grafo tiene 2n(n−1) aristas.
Dibujemos Kn con el menor número posible de cruces y consideremos cada cruce como un nuevo vértice. Obtenemos así un nuevo grafo, denotado por Kn’, que tiene n + cr (Kn) vértices. Como cada cruce de nuestro grafo original Kn ha añadido exactamente dos aristas nuevas, el grafo Kn’ tiene precisamente 2n(n−1)+2cr(Kn) aristas.
K5’ tiene seis vértices y doce aristas (y ningún cruce).
