14/04/18

Quiz: Le ferie del  Topo-logico

Dopo le ultime fatiche per sfuggire ai gatti e riempirsi di buon formaggio, il nostro "Topo-logico" decide di prendersi un periodo di ferie nell'isola di Groviera.

Senza-titolo-1

 

L'isola è scelta per due motivi:

  1. è vietato l'acceso ai gatti.
  2. Nell'isola ci sono molte  città (non importa quante), ognuna con la sua specialità di formaggio.

Il nostro topo-logico è anche  un topo tecnologico; riesce ad imbarcarsi facilmente nell'areo diretto all'isola , e a raggiungere la cabina di pilotaggio.

aereo

Da lì , quando l'aero è vicino all' isola, vede dall'alto le città ,che indichiamo con C1,C2,....Cn-1,Cn

Come scritto nella pubblicità dell'isola di groviera, partendo da una qualsiasi delle città è possibile raggiungere qualsiasi altra città. In pratica tutte e città sono collegate, e le strade sono percorribili in entrambi i sensi di circolazione. Inoltre  c'è una particolarità sul  di numero di strade che entra (o esce) da ogni città.

citta
Qualsiasi sia la città in numero di strade che converge su di essa è pari.

E' sempre un numero pari. Al topo non resta che fare il clandestino su qualche auto, per raggiungere le varie destinazioni.Ma mentre l'aereo sta atterrando, alla radio arriva una notizia di una frana su una delle strade che uniscono le città, ma non si riesce a capire quale. Questo provoca una forte ansia nel topo, che non sa nemmeno dove arriverà l'areo, ma che vorrebbe assaggiare tutte le specialità. Ma il topo-logico ragiona su uno schema mentale e pensa: non ci sono problemi, riuscirò a raggiungere lo stesso tutte le città.

grafo

Come fa il topo ad essere così sicuro? Ha ragione o torto? La domanda potrebbe essere riformulata in tal modo, più preciso e formale:

Supponiamo di avere n città,  tutte collegate da una rete stradale a doppia circolazione, C1,C2,....Cn.(questo significa espressamente che se i, j sono degli indici qualsiasi, esiste sempre un percorso stradale che unisce Ci con Cj. Le strade che convergono su ogni città sono in numero pari. Chiaramente non sappiamo città per città quale sia questo numero . Togliamo una strada a caso; le città rimangono ancora tutte collegate?

P.S. Come nell'altro quiz sul topo logico, può essere utile questo articolo.

 

24 commenti

  1. maurizio bernardi

    Se ho ben capito il significato della domanda, direi che il circuito più "povero" che può collegare tutte le città tra loro, con i due sensi di percorrenza e avendo tutti i nodi con n numero pari di collegamenti, è un semplice anello come quello in figura. ( il percorso in verde gira in senso orario e quello blu in senso antiorario)

    Nel caso che uno qualsiasi dei collegamenti venga interrotto, sarà comunque possibile, partendo da un nodo qualsiasi percorrere tutta la parte di anello fino alla interruzione e tornare indietro verso l'altro capo, toccando tutti i nodi.

    Se, oltre ai collegamenti che costituiscono questo grafo minimo, ne dovessero esistere altri, verrebbero introdotte semplicemente possibili varianti al percorso che abbiamo visto.

  2. maurizio bernardi

    In alternativa al collegamento ad anello potremmo pensare ad un collegamento a stella (che realizza la connessione di tutti i nodi con un ramo in meno rispetto all'anello) come illustrato qui sotto:

    Anche in questo caso tutte le  città  sarebbero collegate (passando dal centro) e, considerando i collegamenti verdi (verso il centro) e blu (verso la periferia) avremmo sempre un numero pari di rami per ciascun nodo, sia che il numero di città sia pari sia che, invece , sia dispari.

    A differenza di prima, però, se una via venisse interrotta, la città raggiunta da quel collegamento resterebbe isolata e non raggiungibile. Se venisse interrotto solo un ramo verde si potrebbe partire dal nodo compromesso e andare verso il centro per poi visitare tutte le altre città. Se fosse invece interrotto un ramo blu occorrerebbe visitare prima tutte le altre città e terminare il giro con il nodo semi-isolato.

    L'interpretazione da dare al fatto che ogni città è raggiunta da due strade (ciascuna a doppio senso di percorrenza ?) porterebbe però a interpretare sia il circuito verde sia quello blu come un tragitto percorribile nelle due direzioni. In questa ultima ipotesi, se una strada verde o una blu venisse interrotta, la configurazione sarebbe comunque sufficientemente ridondante da consentire il collegamento sia in entrata sia in uscita anche per il nodo parzialmente compromesso.

     

  3. Umberto

    Gli esempi che hai fatto sono corretti, ma il quiz richiede di ragionare in termini più generali. Nei tuoi disegni abbiamo due strade diverse che collegano due stesse città; in generale questo non è detto nel quiz; le strade che partono/arrivano da una città sono si pari, ma possono andare su due città diverse. In quanto al discorso del doppio verso di percorrenza, è che non esiste un orientamento fissato; se c'è una strada fra A e B posso andare da A a B o da B a A indifferentemente.

  4. maurizio bernardi

    Riassumo le ipotesi:

    Ogni città è collegata ad almeno altre 2 città . Ogni strada è percorribile nei due sensi.

    Allora , se un qualsiasi collegamento viene interrotto tra due città, queste resteranno collegate ad almeno un'altra città, con la possibilità di andata e ritorno. Pertanto resteranno connesse al sistema e sarà ancora possibile transitare per tutti i nodi del grafo

    Questo detto in modo molto intuitivo e informale.

     

  5. Umberto

    idea non malvagia.. ma faccio fatica a parlare subito.

  6. umberto

    ma.. Che pochi appassionati di formaggio!

  7. Maurizio Bernardi

    come dire... i soliti quattro gatti  ( però, pensandoci, sull'isola non sono ammessi)

  8. io, come amante dei gatti, non posso parlare... farei di tutto per catturare il topolino e portarlo in un'isola piena di gatti: cat island!

  9. Maurizio Bernardi

    Dietro alla metafora del tour dei formaggi, traspare il problema vitale della ridondanza delle reti di comunicazione, emblematicamente delle autostrade telematiche, in cui alle città si sostituiscono i nodi dei provider.

    La geografia ( o topologia) della rete deve prevedere un numero e una dislocazione di collegamenti tali da poter sostenere la connettività anche in situazioni di collasso per picchi di traffico o di interruzione fisica delle connessioni (ad esempio per eventi naturali, come terremoti )

    Non è un problema da poco perché sia i sotto-dimensionamenti sia i sovra-dimensionamenti delle infrastrutture hanno significative ricadute economiche.

  10. umberto

    parole Sante Maurizio.. Sembra un gioco e invece questo tipo di problemi sono proprio alla base della teoria delle reti

  11. Umberto

    un piccolo suggerimento.

    Chiaramente  stiamo parlando di grafi, e tutto quello che abbiamo visto su di essi lo trovate qui.

    Le città sono i nodi del grafo e le strade il lati. Il quiz dunque parla di un grafo connesso in cui i nodi hanno tutti grado pari.

    C'è una importante caratteristica che riguarda la somma dei gradi di un grafo, che supponiamo sempre connesso come nel quiz. Qual'è?

    E' il punto di partenza per la risoluzione.

    PS; almeno la mia soluzione ma penso che siete senz'altro in grado di trovarne delle altre.

  12. Frank

    In effetti appena letto ho subito pensato ad internet e alla sua origine militare, però il problema è diventato molto più complesso e forse quel di sopra può essere vero per i sottosistemi ma per le infrastrutture principali mi pare che non funzioni più. Un esempio lo abbiamo avuto durante la "primavera" egiziana dove qualcuno in pochi secondi ha interrotto le comunicazioni. Rete ideale e reale differiscono parecchio e forse il quesito vero è come interrompere una rete logica perfetta.

  13. Umberto

    per ora abbiamo meno pretese.. ma ne parleremo senz'altro

  14. Maurizio Bernardi

    Potrebbe valere questo ragionamento?

    In un grafo ( connesso ) la somma del numero dei gradi dei nodi è uguale al doppio del numero dei lati.

    Il grafo delle città è per definizione connesso, prima della interruzione di una strada di collegamento tra due città.

    Con l'interruzione il numero dei gradi delle città che usufruivano di quel collegamento diminuisce di una unità, diventando dispari, mentre prima era certamente pari.

    La somma del numero dei gradi dei nodi cala pertanto di due ma resta uguale al doppio del numero dei lati (non interrotti). Quindi il grafo continua a mantenere la caratteristica di essere connesso.

  15. Umberto

    siamo sulla buona strada.. ci siamo quasi.

  16. Maurizio Bernardi

    Non so... potrei aggiungere (ma è implicito) che in un grafo connesso esiste sempre la possibilità di raggiungere qualsiasi nodo, indipendentemente dal punto di partenza, quindi nel nostro caso di passare per tutte le città, anche dopo l'interruzione che si è verificata.

  17. umberto

    il fatto è Maurizio Che un grafo con i nodi pari non è detto che sia connesso..quello del quiz lo é per ipotesi. Almeno se ho ben capito il tuo ragionamento. Se prendi due triangoli separati sono un grafo sconnesso ma tutti i nodi hanno grado pari.Ma vista la prima parte del tuo commento non manca tanto alla soluzione.

  18. Maurizio Bernardi

    Il fatto che il grafo sia  inizialmente connesso, direi iper-connesso, dato che tutte le città hanno inizialmente una connessione multipla, (ogni città è collegata a due o più) e che tutti i nodi hanno grado pari, dovrebbe bastare a dire che anche dopo la interruzione resta connesso.

    Pensando ai due triangoli isolati, che hai citato, se unissi due dei loro vertici con un collegamento, avrei sì un grafo connesso, ma anche 2 nodi con un grado dispari. Ora, se cadesse proprio quel collegamento, il grafo si scinderebbe  di nuovo in due componenti separate.

    La differenza con le città del formaggio è che nel loro grafo non esistono nodi di grado dispari, come quello che ho appena descritto.

  19. Maurizio Bernardi

    Un esempio: se dopo la prima interruzione ( che genera due nodi di grado dispari) se ne verificasse una seconda, penso che non potremmo avere la certezza di poter circolare su un grafo connesso e visitare tutte le città perché potremmo trovarci in una situazione analoga a quella dei due triangoli.

  20. umberto

    si ma non possiamo immaginarci tutti gli esempi. Comunque il tuo pensiero é valido e corretto. La mia dimostrazione é solo più Accademica. Ti pregherei soli di fare un piccolo riassunto dei tuoi pensieri per i lettori. Poi chiudiamo.

  21. Maurizio Bernardi

    Premesso che dal testo del quiz sappiamo che:

     tutte le città sono collegate, e le strade sono percorribili in entrambi i sensi di circolazione. Inoltre  c'è una particolarità sul  di numero di strade che entra (o esce) da ogni città.E' sempre un numero pari.

    ... riassumo sinteticamente il ragionamento, con l'aiuto della figura seguente:

    L'affermazione che ciascun nodo del grafo è di grado pari, equivale a dire che , come minimo, ogni città è collegata  almeno due volte all'insieme di tutte le altre città. In altri termini nessuna città ha un solo collegamento con il resto del grafo.

    Di conseguenza, la rottura di qualsiasi  collegamento (quello blu nella figura) non compromette la connessione che permane grazie all'altro collegamento (verde).

    La conclusione sarebbe che un grafo connesso e non orientato, in cui i nodi hanno tutti grado pari, resta in ogni caso connesso anche a seguito della rimozione di un (solo) collegamento.

    Nel caso venisse rimosso un secondo collegamento, non possiamo avere la certezza che tutti i nodi siano ancora collegabili tra loro (cioè  il grafo sia ancora connesso) in quanto , dopo la prima rimozione, la struttura risulta "indebolita":  uno dei suoi nodi ha  ( potrebbe avere)  ora un unico collegamento con l'insieme degli altri nodi ed proprio quello  il punto di vulnerabilità.

     

  22. Umberto

    Grazie Maurizio, se qualcuno vuole scrivere altro sarei contento.

    La soluzione verrà data nel fine settimana.

  23. Fabrizio

    Se è possibile utilizzare il risultato di Eulero citato nell'articolo "Nove ponti di venezia" la dimostrazione potrebbe essere questa.

    Il risultato di Eulero, per la condizione di sufficienza, ci garantisce che da qualsiasi nodo (A) del nostro grafo integro esiste un percorso chiuso che passa per tutti i lati una ed una sola volta. Preso un qualsiasi altro nodo B, questo sta certamente sul percorso. Inoltre il percorso di andata ed il percorso di ritorno non hanno lati in comune. Poichè i lati sono bidirezionali, il percorso di ritorno può essere percorso in senso inverso. Quindi ci sono due percorsi indipendenti per andare a A a B. L'interruzione di un lato interrompe uno dei due percorsi, ma lascia integro l'altro.

  24. umberto

    quello che dici è senz altro vero Fabrizio. Pensa che stamattina stavo pubblicando la soluzione , cosi faccio a tempo ad inserire anche il tuo pensiero.

Lascia un commento

*

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)

 

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.