Uscire da un labirinto [Topologia]
Ero indeciso se scrivere qui o in Giochi Matematici... semmai posso spostare.
E' ben noto che una volta entrati in un labirinto, per uscirne basta attaccarsi al muro di destra (o quello di sinistra, la questione e' simmetrica ovviamente) e continuare a seguirlo. Buono a sapersi, tra l'altro.
Vi chiedo se avete un bell'argomento semplice e pulito per dimostrare questo fatto.
Sarebbe gradita una "definizione" del termine "labirinto", per cominciare.
Dico quello che mi viene in mente, ci sto pensando anch'io.
E poi, i cannoni sono ammessi (perché no?
)
E' ben noto che una volta entrati in un labirinto, per uscirne basta attaccarsi al muro di destra (o quello di sinistra, la questione e' simmetrica ovviamente) e continuare a seguirlo. Buono a sapersi, tra l'altro.
Vi chiedo se avete un bell'argomento semplice e pulito per dimostrare questo fatto.
Sarebbe gradita una "definizione" del termine "labirinto", per cominciare.
Dico quello che mi viene in mente, ci sto pensando anch'io.
E poi, i cannoni sono ammessi (perché no?
)
Risposte
Penso che come definizione sia semplicemente quella di un qualsiasi albero.
Come si traduce matematicamente la frase "per uscirne basta attaccarsi al muro di destra"?
potremmo vedere il labirinto come un sottoinsieme chiuso connesso per archi di R^2,l'inizio e la fine del labirinto come due punti sulla frontiera e descrivere il "muoversi attaccati al muro di sinistra" come muoversi sulla frontiera;secondo me dovrebbe starci.
a questo punto basta dimostrare che se un'insieme è connesso per archi lo è anche la sua frontiera(non credo sia difficile)
secondo voi può andare?
e se può andare,si può sostituire "connesso per archi" con "connesso"?
a questo punto basta dimostrare che se un'insieme è connesso per archi lo è anche la sua frontiera(non credo sia difficile)
secondo voi può andare?
e se può andare,si può sostituire "connesso per archi" con "connesso"?
Il tuo claim è falso. Prendi una corona circolare: è connessa per archi, ma la sua frontiera è unione di due circonferenze disgiunte...
Dato che il mio hint non è stato recepito lo riscrivo.
Ogni labirinto può essere scritto come un albero. Uscire dal labirinto si scrive come passare da una particolare foglia. Attaccarsi al muro di destra equivale a prendere sempre il primo figlio libero. In pratica il problema del labirinto è equivalente a dire che puoi scorrere tutto l'albero semplicemente prendendo sempre il primo figlio libero (non ancora guardato). Penso che il problema sia semplice. Se si accettano casi in cui il labirinto contiene percorsi chiusi direi che le cose si complicano ma immagino si possa riscrivere il problema nel modo appropriato (devi solo definire destra e devi cambiare il termine albero con grafo e foglia con vertice).
Ogni labirinto può essere scritto come un albero. Uscire dal labirinto si scrive come passare da una particolare foglia. Attaccarsi al muro di destra equivale a prendere sempre il primo figlio libero. In pratica il problema del labirinto è equivalente a dire che puoi scorrere tutto l'albero semplicemente prendendo sempre il primo figlio libero (non ancora guardato). Penso che il problema sia semplice. Se si accettano casi in cui il labirinto contiene percorsi chiusi direi che le cose si complicano ma immagino si possa riscrivere il problema nel modo appropriato (devi solo definire destra e devi cambiare il termine albero con grafo e foglia con vertice).
giusto,e questo controesempio fa saltare anche la connessione.
però su un chiuso che rappresenta un labirinto potremmo mettere un restrizione in piu,cioè che anche il complementare sia connesso..ma a quel punto si deve dimostrare che un labirinto con dei "buchi" è sempre riconducibile a uno senza(cosa intuitivamente vera,ma di difficile formalizzazione,bisognerebbe introdurre una equivalenza fra labirinti coerente e io non sono in grado)
a quel punto credo si possa affermare senza problemi che un chiuso connesso di R^2 con complementare connesso abbia la frontiera connessa; sicuramente è piu facile dimostrarlo se assumiamo che il chiuso in questione abbia anche parte interna connessa(come nel caso dei nostri labirinti).
ma se queste cose si dimostrano solo per la connessione e non per la connessione per archi.. a quel punto credo che qualcuno che distingue meglio di me la connessione dalla connessione per archi debba valutare se basta richiedere la connessione per formalizzare una dimostrazione valida della legge del muro a destra.
edit(non avevo ancora letto il pst di vict85)
che cos'è un'albero in topologia??(sempre che sia possibile spiegarlo in poche righe,se è troppo lungo me lo cerco)
però su un chiuso che rappresenta un labirinto potremmo mettere un restrizione in piu,cioè che anche il complementare sia connesso..ma a quel punto si deve dimostrare che un labirinto con dei "buchi" è sempre riconducibile a uno senza(cosa intuitivamente vera,ma di difficile formalizzazione,bisognerebbe introdurre una equivalenza fra labirinti coerente e io non sono in grado)
a quel punto credo si possa affermare senza problemi che un chiuso connesso di R^2 con complementare connesso abbia la frontiera connessa; sicuramente è piu facile dimostrarlo se assumiamo che il chiuso in questione abbia anche parte interna connessa(come nel caso dei nostri labirinti).
ma se queste cose si dimostrano solo per la connessione e non per la connessione per archi.. a quel punto credo che qualcuno che distingue meglio di me la connessione dalla connessione per archi debba valutare se basta richiedere la connessione per formalizzare una dimostrazione valida della legge del muro a destra.
edit(non avevo ancora letto il pst di vict85)
che cos'è un'albero in topologia??(sempre che sia possibile spiegarlo in poche righe,se è troppo lungo me lo cerco)
Non ho molta dimestichezza con i grafi 
, se ti va Vict potresti formalizzare meglio... Mi ha incuriosito il video (click) che ho trovato su wikipedia (sempre nella pagina linkata da Martino). Credo che con il concetto di omotopia sia possibile arrivare a dimostrare qualcosa.
, se ti va Vict potresti formalizzare meglio... Mi ha incuriosito il video (click) che ho trovato su wikipedia (sempre nella pagina linkata da Martino). Credo che con il concetto di omotopia sia possibile arrivare a dimostrare qualcosa.
Un albero è un grafo che non ha percorsi chiusi http://it.wikipedia.org/wiki/Albero_%28grafo%29 . Che un labirinto possa essere formalizzato come un grafo connesso (a meno che il labirinto non sia in realtà un insieme di labirinti) penso non difficile da comprendere. Ogni incrocio è un vertice del grafo e le varie strade sono gli archi collegati al nodo.
Il punto di partenza è un vertice e anche il punto di arrivo lo è. Che un labirinto sia un albero è più una semplificazione che una cosa inevitabile ma spesso i labirinti sono generati come alberi.
Riguardo ad una dimostrazione formale penso che dovrei pensarci e vedere come definire il tutto.
P.S: quello del video è un labirinto molto particolare.
Il punto di partenza è un vertice e anche il punto di arrivo lo è. Che un labirinto sia un albero è più una semplificazione che una cosa inevitabile ma spesso i labirinti sono generati come alberi.
Riguardo ad una dimostrazione formale penso che dovrei pensarci e vedere come definire il tutto.
P.S: quello del video è un labirinto molto particolare.
Il problema di base è che la regola della mano destra/sinistra non funziona per ogni labirinto. Per farvi un controesempio:
[asvg]noaxes();
var I = [0,0]; dot(I);
text(I, "I", above);
var F = [-3,-1.5]; dot(F);
text(F, "F", above);
line([-1, 1], [1, 1]);
line([-1,1], [-1,0]);
line([1,1], [1,0]);
line([-2, 1], [-2, -1]);
line([-2,-1], [2,-1]);
line([2,1], [2,-1]);
line([-3, 2], [-3, -1]);
line([-3,2], [3,2]);
line([3,2], [3,-2]);
line([3,-2], [-3,-2]);[/asvg]
Supponiamo che siamo già all'interno del labirinto, nel punto I, utilizzando la regola della mano destra, o sinistra, non raggiungeremo mai l'uscita F, gireremmo intorno seguendo sempre lo stesso percorso. E' necessario definire quindi una famiglia di labirinti per cui valga la regola.
[Edit]: Se sto dicendo sciocchezze per favore fermatemi
[asvg]noaxes();
var I = [0,0]; dot(I);
text(I, "I", above);
var F = [-3,-1.5]; dot(F);
text(F, "F", above);
line([-1, 1], [1, 1]);
line([-1,1], [-1,0]);
line([1,1], [1,0]);
line([-2, 1], [-2, -1]);
line([-2,-1], [2,-1]);
line([2,1], [2,-1]);
line([-3, 2], [-3, -1]);
line([-3,2], [3,2]);
line([3,2], [3,-2]);
line([3,-2], [-3,-2]);[/asvg]
Supponiamo che siamo già all'interno del labirinto, nel punto I, utilizzando la regola della mano destra, o sinistra, non raggiungeremo mai l'uscita F, gireremmo intorno seguendo sempre lo stesso percorso. E' necessario definire quindi una famiglia di labirinti per cui valga la regola.
[Edit]: Se sto dicendo sciocchezze per favore fermatemi
"Mathematico":
Il problema di base è che la regola della mano destra/sinistra non funziona per ogni labirinto. Per farvi un controesempio:
[asvg]noaxes();
var I = [0,0]; dot(I);
text(I, "I", above);
var F = [-3,-1.5]; dot(F);
text(F, "F", above);
line([-1, 1], [1, 1]);
line([-1,1], [-1,0]);
line([1,1], [1,0]);
line([-2, 1], [-2, -1]);
line([-2,-1], [2,-1]);
line([2,1], [2,-1]);
line([-3, 2], [-3, -1]);
line([-3,2], [3,2]);
line([3,2], [3,-2]);
line([3,-2], [-3,-2]);[/asvg]
Supponiamo che siamo già all'interno del labirinto, nel punto I, utilizzando la regola della mano destra, o sinistra, non raggiungeremo mai l'uscita F, gireremmo intorno seguendo sempre lo stesso percorso. E' necessario definire quindi una famiglia di labirinti per cui valga la regola.
[Edit]: Se sto dicendo sciocchezze per favore fermatemi
Osserverei 2 cose:
1) La rappresentazione come grafo del tuo labirinto non è un albero.
2) le soluzioni sono multiple.
Ritengo che sia necessario prima di tutto decidere se percorsi chiusi sono ammessi e cioè se quello sia o meno da intendersi come labirinto.
Hai ragione, Vict. Il mio labirinto non è semplicemente connesso 
Non sono sicuro la struttura ad albero sia adeguata a definire un labirinto. Secondo me, Mathematico ha fatto un controesempio calzante: quello è un labirinto a tutti gli effetti, e non vedo come sia rappresentabile con un albero (ma magari mi sbaglio).
Una nota: Martino ha citato la regola della mano dx/sx; ricordo che questa prevede che si esca sempre dal labirinto, ma non a partire da qualunque punto, bensì da un ingresso dello stesso. Quindi nella figura sopra mostrata, partendo da F si raggiunge sempre F, unica entrata ed unica uscita.
Una nota: Martino ha citato la regola della mano dx/sx; ricordo che questa prevede che si esca sempre dal labirinto, ma non a partire da qualunque punto, bensì da un ingresso dello stesso. Quindi nella figura sopra mostrata, partendo da F si raggiunge sempre F, unica entrata ed unica uscita.
"Rggb":
Non sono sicuro la struttura ad albero sia adeguata a definire un labirinto. Secondo me, Mathematico ha fatto un controesempio calzante: quello è un labirinto a tutti gli effetti, e non vedo come sia rappresentabile con un albero (ma magari mi sbaglio).
Una nota: Martino ha citato la regola della mano dx/sx; ricordo che questa prevede che si esca sempre dal labirinto, ma non a partire da qualunque punto, bensì da un ingresso dello stesso. Quindi nella figura sopra mostrata, partendo da F si raggiunge sempre F, unica entrata ed unica uscita.
E' sempre possibile farlo diventare un grafo. Mentre come ho detto la considerazione sugli alberi era una mia limitazione che generalmente è valida e che rende la regola della mano destra sempre valida purché il labirinto sia connesso. Riguardo invece alla tua definizione di uscita non penso sia definibile in termini di teoria dei grafi.
"Mathematico":
Il problema di base è che la regola della mano destra/sinistra non funziona per ogni labirinto. Per farvi un controesempio:
Supponiamo che siamo già all'interno del labirinto, nel punto I, utilizzando la regola della mano destra, o sinistra, non raggiungeremo mai l'uscita F, gireremmo intorno seguendo sempre lo stesso percorso. E' necessario definire quindi una famiglia di labirinti per cui valga la regola.
[Edit]: Se sto dicendo sciocchezze per favore fermatemi
No, hai ragione.
Potremmo limitarci ai labirinti in cui la frontiera è connessa,
e in cui ogni curva chiusa sulla frontiera è riducibile ad un punto o,
equivalentemente, in cui rappresentando ogni incrocio sulla frontiera
con un nodo e disegnando il grafico che la rappresenta, ottengo un albero.
E in quel caso sicuramente esci, ma rimane da fare la dimostrazione
"miniBill":
Potremmo limitarci ai labirinti in cui la frontiera è connessa,
e in cui ogni curva chiusa sulla frontiera è riducibile ad un punto o,
equivalentemente, in cui rappresentando ogni incrocio sulla frontiera
con un nodo e disegnando il grafico che la rappresenta, ottengo un albero.
E in quel caso sicuramente esci, ma rimane da fare la dimostrazione
Salto solo ora nel discorso. Effettivamente la regola della mano sx vale solo per questo tipo di labirinti (secondo Martin Gardner: "semplicemente connessi").
Mi sembra che equivalga in effetti alla ricerca (tipo depth first) sull'albero equivalente.
bye^2, mr
scusate se riapro un vecchio post, ma avrei una domanda: si può applicare questa regola, magari con qualche semplice modifica ad un \(n\)-labirinto (ovvero un labirinto ad \(n\) dimensioni)?
per esempio, come si può uscire da un palazzo a più piani?
conoscete altri algoritmi che possano risolvere il problema? mi viene in mente che qualcosa tipo il filo di arianna funzionerebbe anche in questo caso, ma probabilmente si può fare di meglio.
inoltre (curiosità che immagino sia un problema classico): è possibile calcolare il tempo impiegato per uscire con il migliore degli algoritmi possibili?
per esempio, come si può uscire da un palazzo a più piani?
conoscete altri algoritmi che possano risolvere il problema? mi viene in mente che qualcosa tipo il filo di arianna funzionerebbe anche in questo caso, ma probabilmente si può fare di meglio.
inoltre (curiosità che immagino sia un problema classico): è possibile calcolare il tempo impiegato per uscire con il migliore degli algoritmi possibili?
ciao a tutti ragazzi !
vi propongo un tentativo di soluzione.
ho dato un'occhiata a qualche immagine di labirinto 'poligonale' classico..se in maniera semplicistica lo definissimo come curva semplice, chiusa nel piano?
per esempio consideriamo il labirinto:
La curva 'chiusa caratteristica' è in nero:
la curva contenente è chiusa e semplice, vale il teorema di Jordan ed è omeomorfa ad un quadrato, circuitando il perimetro (a dx o sx) è possibile raggiungere un qualunque punto dello stesso (quindi le entrate o le uscite designate).
Oppure..
La chiusa è di Jordan, l'interno della chiusa caratteristica è semplicemente connesso, la frontiera è connessa per cammini, dunque posso circuitare per cammini qualunque punto ad essa appartenente (entrata ed uscita)
perdonate la poca rigorosità, è tutto trattato 'a naso'
vi propongo un tentativo di soluzione.
ho dato un'occhiata a qualche immagine di labirinto 'poligonale' classico..se in maniera semplicistica lo definissimo come curva semplice, chiusa nel piano?
per esempio consideriamo il labirinto:
La curva 'chiusa caratteristica' è in nero:
la curva contenente è chiusa e semplice, vale il teorema di Jordan ed è omeomorfa ad un quadrato, circuitando il perimetro (a dx o sx) è possibile raggiungere un qualunque punto dello stesso (quindi le entrate o le uscite designate).
Oppure..
La chiusa è di Jordan, l'interno della chiusa caratteristica è semplicemente connesso, la frontiera è connessa per cammini, dunque posso circuitare per cammini qualunque punto ad essa appartenente (entrata ed uscita)
perdonate la poca rigorosità, è tutto trattato 'a naso'
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo