En la actualidad podemos apreciar muchas
cosas que nos pueden parecer de lo más
habitual, caminos, líneas de comunicación
telefónica, televisión por cable, el transporte ferroviario,
líneas aéreas, circuitos eléctricos
de nuestras casas, automóviles, etc. ; lo que no
pensamos frecuentemente es que estos forman parte de algo que
en matemáticas se
denomina como grafos.
En esta monografía se explicara el
Algoritmo de Prim, buscando aplicarlo en problemas reales y
cotidianos, utilizando en general la Teoría de
Grafos.
¿Que es un Grafo?
¿Que es un Grafo?
Un grafo o gráfica es un conjunto finito de
nodos o vértices conectados a través de aristas,
los cuales pueden ser conexos, es decir existe algún
enlace con cada nodo a través de algún camino
formando así un grafo entero; O los grafos no conexos, que
tienen la particularidad de que un segmento de grafo no este
enlazado a través de algún vértice al grafo
principal. En la teoría de grafos existen grafos dirigidos
y grafos no dirigidos , lo grafos dirigidos son aquellos donde
sus aristas tienen un sentido , quiere decir que tienen un
principio especifico en algún nodo y un destino en
algún otro a diferencia de los no dirigidos que son solo
grafos simples (puede tomar ambas direcciones).
Arboles; un árbol es un grafo que no
contiene ciclos y que conecta todos los nodos utilizando el menor
número de aristas posibles.
Árbol recubridor mínimo,
dentro de un grafo se tiene que cubrir todos los nodos formando
un árbol (sub grafo) y utilizando el menor coste posible
(menor costo, tiempo, distancia, precio, etc.)
Descripción del algoritmo
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.
Descripción del algoritmo
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.
probando!