Il problema di Steiner

E se i punti da collegare fossero quattro, disposti ad esempio nei vertici di un quadrato? Si potrebbe pensare di connettere i quattro punti con una X o con una H. In realtà la soluzione ottimale che rende minimo il tracciato è data da una H "schiacciata": man mano che il segmento orizzontale si accorcia, diminuisce anche la lunghezza totale della rete, fino ad un valore minimo. Dopodiché la lunghezza totale torna ad aumentare. Se prendiamo due lastre di plastica trasparente, separate da quattro piccoli pioli, le immergiamo in una soluzione di acqua saponata e, poi, le estraiamo delicatamente, possiamo osservare che si formano delle pellicole di sapone che si dispongono proprio formando angoli di 120 gradi, come nella figura seguente. Successive generalizzazioni portano alla risoluzione di problemi di utilità pratica. L'immagine seguente mostra la rete minima che consente di collegare tra loro 29 città degli Stati Uniti. La risoluzione di questo problema ha richiesto una potenza di calcolo al limite delle attuali possibilità!