Problema dei servizi

Niente fonti!
Questa voce o sezione sull'argomento geometria non cita le fonti necessarie o quelle presenti sono insufficienti.
Abbozzo geometria
Questa voce sugli argomenti geometria e matematica dell'informazione e della comunicazione è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

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 {\displaystyle X_{1},X_{2},X_{3}} e tre pozzi Y 1 , Y 2 , Y 3 {\displaystyle 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 {\displaystyle q} utenti X 1 , X 2 , . . . , X q {\displaystyle X_{1},X_{2},...,X_{q}} e q {\displaystyle q} servizi Y 1 , Y 2 , . . . , Y q {\displaystyle Y_{1},Y_{2},...,Y_{q}} , determinare il grafo ciambellare, ordinario, bipartito, dove ciascun X i {\displaystyle X_{i}} è correlato ad ogni Y i {\displaystyle 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 (1).
  • Problema dei servizi – Studi (2).
    Problema dei servizi – Studi (2).
  • Problema dei servizi – Studi (4).
    Problema dei servizi – Studi (4).
  • Problema dei servizi – Studi (5).
    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

Altri progetti

Altri progetti

  • Wikimedia Commons
  • Collabora a Wikimedia Commons Wikimedia Commons contiene immagini o altri file su problema dei servizi

Collegamenti esterni

  • (EN) three wells problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc. Modifica su Wikidata
  • (EN) Eric W. Weisstein, Problema dei servizi, su MathWorld, Wolfram Research. Modifica su Wikidata
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica