# Tre case e tre centrali

Il problema delle tre case e tre centrali è un problema di topologia privo di soluzione nel piano geometrico, noto in ambito scolastico e spesso proposto scherzosamente a solutori che si dimostrino troppo presuntuosi. Il problema è solitamente presentato nella forma:
"Su una pianura sono presenti una centrale idrica, una centrale elettrica ed una centrale del gas che devono rifornire tre case, anch'esse poste nella pianura. Ciascuna centrale utilizza delle linee di distribuzione (cavi elettrici, gasdotti ed idrodotti) interrate che, per motivi di sicurezza e manutenzione, non possono incrociare quelle di altre centrali. Posto che ciascuna casa deve essere fornita, mediante una linea propria, sia dell'acqua che del gas e della corrente elettrica, riesci a collegare ciascuna centrale a ciascuna casa senza che nessuna linea di distribuzione ne incroci un'altra?"
Tradotto in termini geometrici, il problema consiste nel collegare tre qualsiasi punti di un piano (rappresentati dalle tre centrali) ciascuno con altri tre qualsiasi punti dello stesso piano (rappresentati dalle tre case) mediante delle linee, indifferentemente curve o rette, tali che nessuna di queste ne incida un'altra.
Così come viene posto, il problema lascia supporre esista una soluzione. In realtà è possibile dimostrare che il problema non può essere risolto. Anche se rimaniamo nell'ambito di spazio bidimensionale il problema non ammette soluzione. Mentre se passiamo allo spazio tridimensionale la soluzione può esserci semplicemente applicando una delle 3 centraline al di sotto della casa centrale.

## Soluzione
### Soluzione intuitiva

Supponiamo di avere le tre centrali e le tre case su un piano e di chiamare i punti corrispondenti I per la centrale idrica, G per la centrale del gas, E per la centrale elettrica e quindi C$_1$, C$_2$ e C$_3$ per le tre case.
Supponiamo inizialmente di unire due delle tre case, ad esempio C$_1$ e C$_2$, a ciascuna delle tre centrali. Si formeranno in questo modo i due quadrilateri C$_1$GC$_2$I e C$_1$EC$_2$I, che condividono i lati C$_1$I ed IC$_2$ e compongono a loro volta il quadrilatero C$_1$GC$_2$E. Questa disposizione quindi divide il piano in tre distinte regioni:
* La porzione di piano racchiusa dal quadrilatero C$_1$GC$_2$I
* La porzione di piano racchiusa dal quadrilatero C$_1$EC$_2$I
* La porzione di piano posta al di fuori del quadrilatero C$_1$GC$_2$E
A questo punto la terza casa C$_3$ può trovarsi solo in una di queste tre regioni del piano. Tenendo presente che i quadrilateri citati costituiscono delle linee chiuse piane e che due punti possono essere collegati da una linea che non la intersechi se questi si trovano entrambi all'interno o all'esterno di questa linea chiusa, possiamo distinguere tre possibili situazioni:
* C$_3$ si trova all'interno della regione del piano racchiusa in C$_1$GC$_2$I. In questo caso C$_3$ può essere collegata sia alla centrale idrica che quella del gas ma poiché la centrale elettrica si trova al di fuori di C$_1$GC$_2$I non può essere collegata a questa senza incrociare i condotti che dalle altre centrali vanno a C$_1$ e C$_2$.
* C$_3$ si trova all'interno della regione del piano racchiusa in C$_1$EC$_2$I. In questo caso vale lo stesso ragionamento fatto sopra, con la differenza che la centrale che non può essere raggiunta stavolta è la centrale del gas.
* C$_3$ si trova all'esterno della regione del piano racchiusa in C$_1$GC$_2$E. In questo caso la situazione è ribaltata: C$_3$ può essere collegata alla centrale del gas e a quella elettrica ma non può essere collegata alla centrale idrica, che si trova all'interno di C$_1$GC$_2$E.
Poiché le stesse considerazioni possono essere fatte per ogni altra disposizione delle centrali e delle case, possiamo dire che è impossibile collegare ciascuna casa a ciascuna centrale senza incrociare tra loro almeno due condotti.

### Soluzione formale

Si può notare che il problema consiste nell'individuare un insieme di punti ed un insieme di archi che li colleghino tra loro, ossia nell'individuare il grafo le cui caratteristiche riflettano quelle del problema e stabilire se tale grafo sia un grafo planare, ossia un grafo i cui nodi o vertici siano collegati da archi o lati che non incidono tra loro.
Il grafo del problema è un grafo bipartito completo, ossia un grafo nel quale i nodi sono distinti in due insiemi (le case e le centrali appunto) tali che ciascun nodo di un insieme si collega a tutti i nodi del secondo insieme. In particolare si tratta di un grafo bipartito completo a 3+3 nodi $\,K_{3,3}$, ossia uno dei due grafi di Kuratowski o grafi minori proibiti, i minimi grafi cui possono essere ridotti tutti i grafi non planari. Ne consegue che, poiché il problema fa riferimento ad un grafo non planare, il problema stesso non ha soluzione.