sábado, 14 de mayo de 2011

Algoritmo de Kruskal

Es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo 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.

Archivo:Minimum spanning tree.svg

Un ejemplo de árbol expandido mínimo. Cada punto representa un vértice, el cual puede ser un árbol por sí mismo. Se usa el Algoritmo para buscar las distancias más cortas (árbol expandido) que conectan todos los puntos o vértices.

Algoritmo de Fleury

El algoritmo de fleury encuentra un tour o camino euleriano en un grafo no dirigido, sabiendo si existen por el siguiente teorema:

Sea G un grafo no dirigido y conexo:
- G es euleriano si y sólo si no tiene vértices de grado impar.
- G contiene un camino euleriano si y sólo si tiene exactamente dos vértices de grado impar.


Si es un grafo euleriano.

Algoritmo de Warshall

Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución.
compara todos los posibles caminos a través del grafo entre cada par de vértices.

Dado un grafo G(V, A) dirigido se puede aplicar el algoritmo de Warshall para resolver el problema de si hay o no algún camino que una 2 vértices cualquiera. Para esto necesitamos que el valor de cada arista del grafo sea 0 o 1 indicando si existe camino o no entre los dos vértices que la definen. El resultado de la aplicación de Warshall es la cerradura transitiva de la relación.

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.
 El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo.

Este algoritmo puede adaptarse fácilmente para resolver problemas de caminos de longitud mínima en grafo dirigidos.

Archivo:Dijksta Anim.gif