7.3.07

Laberintos (Parte 6)

(A la parte 5 - A la parte 7)

Postulados

Vamos a comenzar a establecer algunos postulados que, razonablemente, deberá cumplir cualquier método que se proponga para medir la dificultad de un laberinto.

Postulado 1: La dificultad de un laberinto es un número real mayor o igual que cero. (Obviamente, cuanto mayor sea el número más difícil es el laberinto.)

Postulado 2: La dificultad del laberinto trivial es cero.

Por laberinto trivial entendemos el laberinto que tiene solamente dos nodos (entrada y salida) unidos por un único eje.

Antes de enunciar el tercer postulado imaginemos que los grafos están formados por cuentas de colores unidas por hilos, e imaginemos también que podemos mover las cuentas estirando o contrayendo los hilos tanto como se quiera, sin cortarlos y sin despegar o unir cuentas. Dos grafos se dirán equivalentes si pueden obtenerse uno del otro por medio de las transformaciones que acabamos de describir (como antes, es posible dar definiciones más rigurosas de estos conceptos, pero para todos nuestros fines estas definiciones intuitivas serán más que suficientes).

Por ejemplo, en el dibujo siguiente, los grafos A y B son equivalentes entre sí, pero C no es equivalente a ninguno de los otros dos:
Postulado 3: Dos grafos equivalentes tienen la misma dificultad. (En otras palabras, la dificultad es un invariante topológico de un laberinto.)

En la próxima parte veremos otros postulados que deberán respetarse al medir la dificultad de un laberinto.

(A la parte 5 - A la parte 7)

2 comentarios:

Santiago dijo...

Hola Gustavo, una serie interesante, como siempre. Un detalle, ¿un nodo al que sólo llegan dos caminos (entrada y salida), vale la pena contarlo? (p. ej. el que sigue a la partida en el último dibujo?

Saludos

Gustavo Piñeiro dijo...

En efecto, no vale la pena. De eso justamente va a tratar la entrada siguiente (que ya tengo escrita, pero que todavía no tuve tiempo de "subir".)