I grafi completi
--------------------
In combinatoria, un
grafo è un insieme di punti (i
vertici) alcuni dei quali sono collegati tra loro da linee (gli
archi). La forma geometrica delle linee non conta: contano soltanto i vertici che esse permettono di collegare (vedi
les Graphes,
Bibliothèque Tangente 54, 2015).
Un grafo si dice completo quando ciascuno dei suoi vertici è collegato a tutti gli altri. Il grafo completo con n vertici si indica con Kn.
[/encadre]
Primi schizzi
-------------------
Il grafo completo con due vertici, indicato con K2, non presenta alcuna difficoltà: basta tracciare un segmento fra due punti. Il caso di K3 non è più difficile: si disegna semplicemente un triangolo; ciascuno sceglierà quello che gli sembra più estetico… Con quattro vertici, la questione degli incroci comincia a porsi. La rappresentazione più abituale è la seguente, nella quale compare un incrocio.
Disponendo diversamente i punti, oppure tracciando archi «meno rigidi», si possono tuttavia evitare gli incroci. Il numero minimo di incroci di K4 è dunque, di fatto, nullo. Si scrive: cr (K4) = 0.
Passiamo al caso del grafo completo con cinque vertici. Dopo qualche tentativo, sembra inevitabile che gli archi si incrocino almeno una volta… Ma ne siamo certi?
Si può dimostrare che cr (K5) = 1, ossia che ogni rappresentazione di K5 nel piano richiede almeno un incrocio. In realtà, sfruttando con astuzia alcuni risultati fondamentali della teoria dei grafi, possiamo spingerci anche oltre. Consideriamo il caso generale del grafo completo Kn. Ciascuno dei suoi vertici è collegato agli altri n – 1, e ogni arco collega due vertici. Questo grafo ha dunque 2n(n−1) archi.
Disegniamo Kn con il minor numero possibile di incroci e consideriamo ciascun incrocio come un nuovo vertice. Otteniamo così un nuovo grafo, indicato con Kn’, che possiede n + cr (Kn) vertici. Poiché ogni incrocio del nostro grafo originario Kn aggiunge esattamente due nuovi archi, il grafo Kn’ ha precisamente 2n(n−1)+2cr(Kn) archi.
il K5’ ha sei vertici e dodici archi (e nessun incrocio).
