Problema dei servizi

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

Il quesito si generalizza con il seguente enunciato:

« Dati q utenti X_1, X_2,..., X_p 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.

Bibliografia[modifica | modifica sorgente]

  • 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[modifica | modifica sorgente]

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