Un problema de ciudades y carreteras
Grafo coloreado
Este tipo de problemas se puede solucionar por "fuerza bruta", tomando un punto cualquiera de partida (si pasas realmente por todos y vuelves al inicial, da igual por cuál empieces) y procurando seguir todos los posibles caminos, hasta descartar que exista, lo que llevaría un cierto tiempo, ya que habría que descartar todas las posibilidades, o bien encontrar uno, que en esta ocasión no existe.
El truco que usaron los que propusieron el problema consiste en colorear el grafo de una forma similar a la de la imagen. Se colorean de colores diferentes aquellos nodos que tienen una carretera que los conecte. Si es posible hacerlo, se le llama grafo bipartito. Bueno, pues está claro de que si es un grafo bipartito, recorrer todos los nodos sin repetir usa la misma cantidad de nodos de los dos colores, ya que pasas de uno a otro cada camino. Pues bien, eso no es posible en nuestro grafo porque hay diferente cantidad de nodos de cada color.
No hay comentarios:
Publicar un comentario