ies marco do camballón

bbb-Ben..., o máis importante dun labirinto é como se conectan as encrucilladas. A lonxitude dos túneles é irrelevante.
bbb-Temo que non coincido con esa opinión -dixo Teseo compunxido, rascándose un calo.
bbb-O que quero dicir é que a lonxitude afecta só ao longo do camiño, mais non ao camiño que tomas para saír; de acordo? Agora podemos representar os elementos topolóxicos esenciais mediante un grafo: os seus nodos corresponden ás encrucilladas do labirinto e as súas arestas corresponden aos túneles. Entón o problema de saír do labirinto (ou de atopar un lugar concreto no seu interior) convértese no problema de atravesar un grafo dun nodo a outro.
bbb-Creo que todos sabemos iso -dixo Teseo.
bbb-Si, pero realmente hai un teorema preciso que di cando é posible.
bbb-Estupendo! -dixo Teseo-. Adoro os teoremas. Pitágoras contoume un realmente sorprendente, algo sobre un hipopótamo cadrado...
bbb-Non me refiro a ese, Teseo. Este é un teorema sobre grafos. Dous nodos poden ser unidos por un camiño continuo se -e só se- xacen na mesma compoñente conexa do grafo.
bbb-Hummm -dixo Teseo, dubitativo-. E que é unha compoñente conexa?
bbb-O conxunto de todos os nodos aos que se pode chegar a partir dun dado por un camiño continuo -dixo o Minotauro orgullosamente.
bbb-Ah. Déixame ver se entendín ben isto. O que ti estás dicindo é que dous nodos poden ser unidos por un camiño continuo se -e só se- existe un camiño continuo que os une?
bbbO Minotauro estaba profundamente ofendido.
bbb-Ben... poderías dicilo así, mais paréceme que estás banalizando un concepto importante.
bbb-Quizá. Mais creo que necesitamos algo un pouco máis instrutivo.
bbb-Oh, moi ben. Ti queres un algoritmo para seguir labirintos.
bbb-Queres dicir o fabuloso Algorithmos labyrinthoi, o monstro de noventa cabezas con dentes afiados e cabeleira de gorgona que mora nos antigos pasadizos?
bbb-Non, Teseo, non se trata dunha besta mítica. É só unha palabra que a xente vai inventar. Recibirá o seu nome de Muhammad ibn Musa abu Abdallah al-Khorezmi al-Madjusi al-Qutrubilli. "Al-Khorezmi" convertirase en "al-Gorizmi", logo "algorismo", e finalmente "algoritmo". Será moi útil para describir un procedemento específico que permita resolver un problema.
bbb-Brillante! -berrou Teseo-. Esta idea asegurará a nosa liberdade! Si, Minotauro, non esquecín a túa teoría pesimista de que estamos atrapados para sempre por designio dos deuses; pero nin sequera o Olimpo pode interferir no funcionamento da lóxica, senón os deuses destruirían a base mesma do universo e, con iso, o seu propio propósito. Estamos salvados! Todo o que temos que facer é executar unha Procura en Máxima Profundidade do labirinto!
bbbPero o Minotauro parecía pouco entusiasta.
bbb-O problema, Teseo, é que para aplicar a Procura en Máxima Profundidade necesitas algunha forma de marcar cada encrucillada para que saibas se estiveches antes aí e de onde viñas. Deuche por casualidade Ariadna unha barra de xiz ademais do fío?
bbbTeseo admitiu que o xiz faltaba inexplicablemente no seu equipamento.
bbb-Con todo, teño unha espada. Raiarei as paredes.
bbb-Non é posible, estas rochas son tan duras como o diamante.
bbb-Carallo!
bbbSentaron en silencio, en íntima comuñón cos seus sombríos pensamentos.
bbb-Supoño que ti inventaches o algoritmo SUAM, ou Solución Universal da Adiviña do Minotauro -dixo Teseo-. Pero o que realmente necesitamos é un método universal que nos saque de calquera labirinto e non implique facer marcas nas paredes do labirinto.
bbb-Non hai ningunha esperanza -dixo o Minotauro-. Ninguén sería capaz de pronunciar o algoritmo HIMUQNSDCLYNIHMELPDL.
bbb-Non sexas sarcástico -dixo Teseo con amargura, mais de súpeto deu un salto e púxose en pé excitado-. Espera! A túa longa secuencia de letras deume unha idea... Si! Mira, sabemos que existe unha secuencia de xiros a esquerda e dereita que nos sacará dun labirinto concreto. De modo que quizá haxa unha secuencia de xiros a esquerda e dereita que nos saque de calquera labirinto. Só unha secuencia: a mesma para todos os labirintos! Algo como EEEDDEDEDDEDDDDDE... Terá que ser infinitamente longa porque hai infinitos labirintos posibles. Chamareina o algoritmo SULT: Solución Universal para Labirintos de Teseo.
bbb-Absurdo! Para empezar, algunhas encrucilladas poderían ter máis de dous camiños posibles. Se tes que seguir recto, entón unha elección só entre esquerda e dereita non serviría, non? E que sucede coas rúas cegas?
bbb-Podo evitar iso facilmente -dixo Teseo, sorrindo de orella a orella-. A elección será entre "dereita" e "esquerda" só cando en cada encrucillada se atopen exactamente tres túneles: aquel polo que ti te achegas á encrucillada, máis os outros dous en que este se bifurca.
bbb-Mais pode que non sempre sexan tres -protestou o Minotauro.
bbb-Ah, pero eu podo reducir calquera grafo, e polo tanto calquera labirinto, a un que teña só encrucilladas triplas. Simplemente substitúo unha encrucillada múltiple por un anel de encrucilladas triplas enlazadas e engado un lazo pechado a cada rúa cega. Ah!, e se hai unha encrucillada "falsa", na que só se atopan dúas arestas, bórroa. En consecuencia, a partir de calquera grafo podo formar un grafo modificado só con encrucilladas triplas. Se podo atravesar o grafo modificado, entón resúltame doado reconstruír un xeito de atravesar o grafo orixinal contraendo a puntos as cousas que engadín.
Iso acabou coa obxección do Minotauro, pero aínda quedaba unha dificultade menor: atopar unha secuencia universal para solución de labirintos de xiros esquerda e dereita.
bbb-Hummm -dixo Teseo finalmente-. Supoñamos que fago unha lista de todos os labirintos posibles.
bbb-Si! Si! -interrompeu o Minotauro, cuxos ollos chispeaban co resplandor da súa repentina idea-. Primeiro fas a lista de todos os labirintos (ou grafos) con dous nodos, logo os de tres, logo os de catro, e así sucesivamente, contando só os grafos que teñen encrucilladas triplas, por suposto. Entón encadeas todas as listas, unha despois doutra.
bbbTeseo preguntábase se iso era ou non posible.
bbb-Que pasa se hai infinitos grafos para certo número de nodos? Entón a túa lista faise infinita e non hai ningún "despois" onde empatar a lista seguinte.
bbb-Ah, pero o número de grafos distintos cun número finito dado de vértices é sempre finito.
bbb-Por que?
bbb-Ti podes representar calquera grafo de n xeitos por unha matriz n x n de ceros e uns. Simplemente numeras os nodos de 1 a n, e logo fas a entrada na fila r e columna c da matriz igual a 1 se os nodos r e c están unidos por unha aresta, e 0 se non o están. A matriz especifica por completo as conexións do grafo. E o número de posibles matrices n x n de ceros e uns é 2n2, que é finito.
bbb-Correcto... De modo que o número de grafos diferentes de n nodos é menor ou igual a iso, polo tanto tamén é finito -dixo Teseo-. Avanzamos, Minotauro; agora véxoo todo. Unha vez que ti fixeches a lista de todos os posibles grafos de labirinto en orde de complexidade, consideras o primeiro, escolles un lugar de partida e un punto de saída nel, e calculas que secuencia de esquerdas e dereitas te sacaran del. Esa será unha secuencia finita.
bbb-Si, pero que pasa se empezas nalgún outro lugar do labirinto? Ou se necesitas atopar unha saída diferente?
bbb-Ese é o punto máis hábil. Ti escolles un comezo e unha saída diferente no primeiro grafo, e ves onde chegaría a secuencia anterior se non estiveses no lugar do que partiches orixinalmente...
bbbHoubo unha longa pausa mentres o Minotauro dixería isto. Teseo estaba a piques de falar novamente, pero o Minotauro interrompeuno.
bbb-Se iso te saca, ben; se non, ti engades outra secuencia que o fará. Desde logo. E entón continúas facéndoo para todas as outras combinacións de puntos de partida e saída no primeiro labirinto, non si?
bbb-En efecto. Tal vez haxa outro xeito máis eficiente, pero este funciona. E cando remates, pasas ao segundo labirinto e amplías a secuencia para traballar con todos os puntos de partida e saída posibles, un tras outro; logo pasas ao terceiro labirinto, e así sucesivamente.
bbbO Minotauro pensou moito antes de preguntar lentamente:
bbb-Entón, hai infinitas posicións e labirintos, non é así, Teseo?
bbb-Si, pero como ti mesmo observaches, aínda podemos escribilos en orde como unha lista infinita, e iso é todo o que necesitamos.
bbb-Si, Teseo, véxoo. Pero se eu podo facer unha lista deste conxunto infinito de labirintos e posicións de partida, entón podo facer a lista en calquera orde, ou non?
bbb-Supoño...
bbb-Ben, entón, non podo facer a lista deles de xeito que todos os labirintos dos que se poida saír facendo só xiros a esquerda estean ao principio, e polo tanto que a miña secuencia empece con infinitos xiros á esquerda: EEEEEE...?
bbbTeseo sentiu un lixeiro desacougo, pero antes de que puidese expresalo, o Minotauro lanzouse ao interior do labirinto. A súa voz, cada vez máis feble, reflectíase nas paredes do túnel: "Esquerda... esquerda... esquerda... esquerda..."
bbbPresa dun pánico repentino, non tanto preocupado pola lóxica do argumento como asustado de quedar atrás, Teseo tamén botou a correr, pero a el podía oírselle gritar: "Dereita... dereita... dereita... dereita..."
bbbDespois dunha ou dúas horas, Teseo deixou de virar á dereita. Ollou coidadosamente ao seu redor para estar seguro de que non era observado, colocou con precaución a súa man esquerda no muro e reiniciou o percorrido do labirinto. Ao cabo dun intre cruzouse co Minotauro, que andaba con dificultade cos dous pezuños esquerdos apoiados na parede oposta, viaxando en dirección contraria. Ambos parecían moi incómodos e evitaron o contacto visual cando se cruzaron, simulando estar absortos nos seus profundos pensamentos.