Este problema surge de la
necesidad de encontrar dentro de un grafo no dirigido, un árbol que recorra
todos los nodos del grafo, y cuya suma de los pesos o valores de las aristas
sea menor entre todos los arboles que se puedan formar en el grafo en cuestión.
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol de cobertura mínimo dentro de un grafo no dirigido. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Ejercicio:
Primero elegimos un nodo que
tomara la función de nodo raíz y lo señalamos.
Luego se encuentran las
aristas que estén conectadas al nodo raíz.
De las aristas encontradas se
procede a determinar cual es la que tiene menor peso y se la señala.
En el caso de encontrarse con
aristas que tengan el mismo peso se procede a seleccionar una de ellas de forma
aleatoria.
Luego se vuelve a comparar los pesos entre los nodos relacionados, en este caso A-C, como los pesos son iguales son iguales se puede escoger cualquier arista.
Se vuelve a marcar el nodo que resultó estar conectada a la arista y se repite de forma continua los mismos pasos hasta tener un árbol que una todos los vértices.
Algoritmo de Kruskal
De igual forma el algoritmo de
kruskal es un algoritmo de la teoría de grafos, que es utilizado para encontrar
el árbol de cobertura mínimo dentro de un grafo determinado.
Es decir, busca un subconjunto
de aristas que, formado un árbol, incluyen todos los vértices y donde el valor
total de todas las aristas del árbol es el mínimo. Ejercicio:
Primero procedemos a determinar de entre todos los nodos las aristas cuál es la arista que tiene el menor peso y la seleccionamos.
Procedemos a señalar la arista y los vértices que une tomando en cuenta lo explicado anteriormente.
Realizamos el mismo
procedimiento, encontramos el valor menor de los pesos y marcamos los vértices
que una dicha arista.
Si podemos observar, se vuelve
a generar el inconveniente anterior así que elegimos el valor que le sigue.
En el caso de que el valor que
le siga se repita, se puede escoger cualquiera de las dos aristas, tomando en
cuenta que no se debe generar un lazo cerrado.
En la gráfica se puede observar
que las dos aristas coinciden en un punto, pero es necesario aclarar que no se
genera un lazo cerrado ya que solo son trayectorias que están pasando por un
lugar en común más no están en ningún momento en intersección.
El árbol expandido que se genera es el siguiente:
La aplicación de estos problemas de optimización dentro de nuestra especialidad y nuestro diario vivir se ubica en las redes de comunicación eléctrica, telefónica, carretera, ferrovía, aérea, marítima, etc., donde los nodos representan puntos d consumo eléctrico, teléfonos, aeropuertos, computadoras, y las aristas podrían ser de alta tensión, cable de fibra óptica, rutas aéreas, etc.
No hay comentarios:
Publicar un comentario