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.
L'isola è scelta per due motivi:
- è vietato l'acceso ai gatti.
- 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.
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à.
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à.
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
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.
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.
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.
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.
idea non malvagia.. ma faccio fatica a parlare subito.
ma.. Che pochi appassionati di formaggio!
come dire... i soliti quattro gatti ( però, pensandoci, sull'isola non sono ammessi)
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!
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.
parole Sante Maurizio.. Sembra un gioco e invece questo tipo di problemi sono proprio alla base della teoria delle reti
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.
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.
per ora abbiamo meno pretese.. ma ne parleremo senz'altro
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.
siamo sulla buona strada.. ci siamo quasi.
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.
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.
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.
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.
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.
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à.
Grazie Maurizio, se qualcuno vuole scrivere altro sarei contento.
La soluzione verrà data nel fine settimana.
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.
quello che dici è senz altro vero Fabrizio. Pensa che stamattina stavo pubblicando la soluzione , cosi faccio a tempo ad inserire anche il tuo pensiero.