Ejercicio de Habilidad Lógico-Matemática — UNMSM
En un plano se muestran ocho edificios multifamiliares (regiones sombreadas) y las calles que quedan entre ellos (regiones sin sombrear). Una persona, ubicada en el punto P, desea recorrer todas las calles de este condominio. ¿Cuántas calles, como mínimo, debe recorrer más de una vez para lograr su propósito?
Ver solución paso a paso
- Modelar el plano de calles como un grafo, en el que las esquinas son vértices y las calles son aristas.
- Contar los vértices de grado impar del grafo: se identifican 12 vértices impares.
- Recordar que, para completar un recorrido que cubra todas las aristas repitiendo el mínimo posible, el número de repeticiones necesarias es , donde es la cantidad de vértices de grado impar.
- Calcular: segmentos repetidos; sin embargo, al analizar el grafo con detalle, esos 5 segmentos corresponden en realidad a solo 4 calles distintas del condominio (una de las calles concentra dos de esas repeticiones).
- Por lo tanto, la cantidad mínima de calles que deben recorrerse más de una vez es 4.