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.



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.

Teoría de grafos

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos.

Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas.

Se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Isomorfismo

Un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices.

La función es biyectiva si es al mismo tiempo inyectiva y sobreyectiva; es decir, si todos los elementos del conjunto de salida tienen una imagen distinta en el conjunto de llegada.

y a cada elemento del conjunto de llegada le corresponde un elemento del conjunto de salida.

 Una función es inyectiva si a cada valor del conjunto X le corresponde un valor distinto en el conjunto Y de f.

Es decir, a cada elemento del conjunto X le corresponde un solo valor de Y tal que, en el conjunto X no puede haber dos o más elementos que tengan la misma imagen.

 

  f: V(G) =  V(H)

que preserva la relación de adyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H.

Una función es sobreyectiva cuando la imagen, elemento de "Y" es la imagen de como mínimo un elemento de "X".

Aristas dirigidas y no dirigidas

 Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente:

Una arista corresponde a una relación entre dos vertices de un grafo. Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

Gráficamente las aristas se representan, para el caso de los grafos no dirigidos, como una línea que une a los dos vértices. Si el grafo es dirigido, entonces la arista se representa como una flecha, que parte del nodo origen y apunta al nodo destino

Vértice

Los vértices constituyen uno de los dos elementos que forman un grafo. Un vértice o nodo es la unidad fundamental de la que están formados los grafos.

El grado de un vértice en un grafo es el número de aristas incidentes a él. es decir  el grado o valencia de un vertice es el número de aristas incidentes al vértice