investigacion de operacion

1. Algoritmo de Prim o Algoritmo de Kruskal.
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubierto mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetados.
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 árboles el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubierto mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmoes también conocido como algoritmo DJP o algoritmo de Jarnik.
El algoritmo de Prim encuentra un árbol de peso total mínimo conectando nodos o vértices con arcos de peso mínimo del grafo sin formar ciclos. Al igual que el algoritmo de Kruskal, el de Prim también ha sido aplicado para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones, TV porcable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial, análisis de imágenes, extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros).
Consiste en dividir los nodos de un grafo en dos conjuntos: procesados y no procesados. Al principio, hay un nodo enel conjunto procesado que corresponde al equipo central; en cada interacción se incrementa el grafo de procesados en un nodo (cuyo arco de conexión es mínimo) hasta llegar a establecer la conexión de todos los nodos del grafo a procesar.
Funciona de la siguiente manera:
• Se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado.
• Se crea un conjunto Cque contenga a todas las aristas del grafo mientras C es no vacío.
• Eliminar una arista de peso mínimo de C.
• Si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol.
• En caso contrario, se desecha la arista.
Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.
Este algoritmofue publicado por primera vez en Proceedings of the American MathematicalSociety, pp. 48–50 en 1956, y fue escrito por Joseph Kruskal.

3. Algoritmo de Dijkstra
El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere aEdsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de labúsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de coste negativo.
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuandola de x que se debe colocar en 0 debido a que la distancia de X a X sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos nodos no marcados vi.
4. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la...