Problema dei servizi

In topologia e teoria dei grafi, il problema dei servizi affronta questioni che si richiamano al classico quesito:

«In una pianura vi sono tre case $X_{1},X_{2},X_{3}$ e tre pozzi $Y_{1},Y_{2},Y_{3}$ . Tracciare delle strade, da ciascuna casa a ciascun pozzo, senza che alcuna di esse si intersechi mai fuori dei pozzi e delle case.»

Apparentemente di immediata soluzione, il problema delle tre case e dei tre pozzi fa sorridere gli ingenui, ma fa pensare i matematici. La soluzione è possibile soltanto se i tre soggetti sono disposti a costruire un cavalcavia in modo che almeno uno di loro vi passi sotto ed un altro vi passi sopra.

Il primo matematico a affrontare e risolvere esaustivamente questo problema è stato Fermat, nel 1643, che ne pubblicò la soluzione trovata accidentalmente durante uno studio sulla fattorizzazione grafica dei grandi numeri.

Generalizzazione

Il quesito si generalizza con il seguente enunciato:

«Dati $q$ utenti $X_{1},X_{2},...,X_{q}$ e $q$ servizi $Y_{1},Y_{2},...,Y_{q}$ , determinare il grafo ciambellare, ordinario, bipartito, dove ciascun $X_{i}$ è correlato ad ogni $Y_{i}$ e viceversa.»

Per grafo ciambellare si intende tracciato su ciambella; per grafo ordinario si intende non "intrecciato", cioè ogni arco ha in comune con altri archi soltanto i nodi estremi.

Problema dei servizi – Studi (1).
Problema dei servizi – Studi (2).
Problema dei servizi – Studi (4).
Problema dei servizi – Studi (5).

Bibliografia

Luigi Muracchini, Introduzione alla teoria dei grafi, Torino, Boringhieri, 1967.
Romano del Nord, I modelli grafo-matematici e la progettazione, Firenze, CLUSF (Cooperativa Libraria Universitaria), 1972.

Voci correlate

Tre case e tre centrali

Altri progetti

Wikimedia Commons contiene immagini o altri file su problema dei servizi

Collegamenti esterni

(EN) three wells problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
(EN) Eric W. Weisstein, Problema dei servizi, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica