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 (conexiones
cerradas).
 |
| E-F es
la aristas más corta, por lo tanto se la resalta. |
 |
| C-H y F-G son las siguientes en la lista, al
no formar un ciclo se las seleccionan simultáneamente. |
 |
| Las
siguientes aristas son las de peso 5, G-H
y G-I. |
 |
| Aquí
se marcan las aristas A-B y D-E pero no F-I porque si se eligiese se formaría un ciclo. |
 |
| Continuando
con la lista, seguiría el peso 7, pero como formaría un ciclo la descartamos,
siguiendo así con la arista siguiente A-G. |
Concluyendo con los pasos del método, así quedaría el árbol generador
mínimo del grafo anterior. Este tiene un peso total de 40.
Método de Prim
A diferencia del método de Kruskal, se
parte desde un vértice arbitrariamente escogido. Luego se busca el menor peso
de las aristas adyacentes, evitando la formación de ciclos. Esto se realiza
hasta abarcar todos los vértices del grafo.
 |
| Arbitrariamente, decidimos empezar por el vértice
G, y partimos hacia F por ser el de menor peso. |
 |
| Se resalta el elemento adyacente menor, entre
los vértices, ya conectados. |
 |
| Ya que las aristas G-H y G-I no forman
ciclos, se las marca simultáneamente. |
 |
| La arista C-H
con peso 4 es la menor. |
 |
| Aquí
se marca la arista D-E pero no F-I porque si se eligiese se formaría un
ciclo. |
 |
| De la misma que en el paso anterior no se escoge
la arista F-I, por esto se escoge A-G. |
|
| Por último, la arista a resaltar es A-B. |
Como podemos
observar, los arboles generadores mínimos son iguales en las aristas
seleccionadas. Esto puede pasar como no, pero con respecto al peso mínimo, este
siempre será el mismo para cualquier método utilizado.
Bibliografía:
Rosen, K. (2004). Matemática
Discreta y sus Aplicaciones. Madrid: McGraw-Hill Interamericana de España.
