Árbol generador
En línea con los problemas 35 y 36 de la separata (páginas 68 y 69), y como una propuesta de problema de árbol generador para complementar esos ejercicios, podría proponerse algo relacionado al tendido de cables en una ciudad (más bien en un barrio en principio), del siguiente estilo:
“Una empresa debe renovar el cableado eléctrico que abastece un barrio y hacerlo subterráneo, y para eso tiene un costo fijo por cada x metros que extienda del mismo. El siguiente grafo representa en las aristas las distancias entre los puntos de conexión necesarios. ¿Cómo sería conveniente realizar el tendido para asegurar a todo el barrio el servicio, con el menor costo en cableado?” (Y bueno, acá iría un dibujito, más o menos acorde).
¿Estoy en onda con la idea? Porque de ser así quizás se puede afinar un poco el problema, y sino reseteo.
Yes, es la idea.
ResponderEliminarSupongo que en el grafo pondrás las distancias entre vértices.
1. Una variante es decir que los costos dependen de otros factores, no sólo distancia (a lo mejor hay una línea de gas/agua/cloaca que hay que evitar en algunas partes).
2. Lo que tendría sentido es dar la distancia/costo entre cualquier par de puntos de conexión. Salvo que haya muy pocos vértices, no se pueden poner los costos en el mismo dibujo. ¿Cómo se puede hacer?
He encontrado problemas similares a éste que en lugar de dar el grafo presentan la información en forma de tabla de doble entrada, entonces ahí no se hace lío si hay tantos vértices y no quedaría confuso el gráfico.
ResponderEliminarMe imagino que te referís a la "matriz de adyacencias", donde la entrada ij (entre vértice "i" y vértice "j") indica el costo de ir de "i" a "j". En general para pocos vértices (¿no más de 7/8?) el gráfico está bien, la matriz se puede manejar si se la puede ver en una página (si tanto), pero en general si noy ha demasiadas aristas (el grafo es "ralo"), es mejor poner lista de aristas o de vecinos.
EliminarMe gusta el problema Mayra!
ResponderEliminar