title: Problema dei servizi
text: # 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).
  