Apr 14

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

    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à.

     

  2. Umberto

    Grazie Maurizio, se qualcuno vuole scrivere altro sarei contento.

    La soluzione verrà data nel fine settimana.

  3. 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.

  4. 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)