Laberintos (Parte 7)

(A la parte 6 - A la parte 8)

Más postulados

Algún tiempo atrás vimos un laberinto y un grafo que servía para representarlo (el grafo A del dibujo de más abajo):

Pero si bien se mira el grafo B también representa el mismo laberinto. Por lo tanto, aunque A y B no son equivalentes, es razonable que tengan la misma dificultad. Observemos que A se obtiene de B agregando tres nodos a lo largo de uno de sus ejes. Tenemos entonces:

Postulado 4: Si el grafo A se obtiene agregando nodos a lo largo de uno de los ejes de un grafo B entonces A y B tienen la misma dificultad.

(A la parte 6 - A la parte 8)