Aplicación de estrategias de recorrido de grafos en la vida real
Introducción Dentro de la construcción de una casa llega un momento donde se tienen que armar las bocas de luz donde irían los enchufes y/o llaves de iluminación. Por cada uno de estos puntos debe pasar cierto cable ¿Cuál es la manera más óptima para realizar el cableado? Este problema puede ser modelado a través de un grafo y resuelto buscando el árbol generador mínimo. Se llama árbol generador mínimo de un grafo ponderado (distancias/pesos de las aristas) al árbol generador tal que la suma de los pesos de las aristas sea la mínima entre todos sus árboles generadores. Dado el siguiente grafo, se explicará cómo se llegó a la solución a través de los métodos de Kruskal y de Prim. Método de Kruskal En este procedimiento se ordenan las aristas por su peso para elegir la menor. Y se iterará hasta que todos los vértices sean alcanzados por una arista, controlando a su vez, que no se provoquen ciclos (conexi...