domingo, 29 de septiembre de 2013
ALGORITMO DE KRUSKAL
El Algoritmo
de Kruskal es un algoritmo de la teoría de gráficos para encontrar un árbol recubridor
mínimo en un gráfico conexo y ponderado. Es decir, busca un
subconjunto de aristas que, formando un árbol, incluyen todos los vértices y
donde el valor total de todas las aristas del árbol es el mínimo. Si el gráfico
no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido
mínimo para cada componente conexa).
El algoritmo de Kruskal es un ejemplo de algoritmo voraz.
sábado, 28 de septiembre de 2013
ALGORITMO DE FORD FULKERSON
El Algoritmo
de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo
máximo. Es aplicable a los "Flujos Maximales". La idea es encontrar una ruta de penetración con un flujo positivo neto
que una los nodos origen y destino. Su nombre viene dado por sus creadores, L.
R. Ford, Jr. y D. R. Fulkerson.
ALGORITMO DE DIJKSTRA
El
Algoritmo De Djkstra, también llamado
“Algoritmo De Caminos Minimos”, es
un algoritmo para la determinación del camino más corto dado un vértice origen
al resto de vértices es un gráfico con pesos en cada arista. Su nombre se
refiere a Edsger 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 gráfico, el algoritmo se detiene.
Suscribirse a:
Entradas (Atom)