Grafos ponderados

Un grafo simple G=(V, A) (grafo simple dirigido, respectivamente) es un grafo ponderado si tiene asociado una función W: A->R llamada función de ponderación, es decir que se pone el valor del peso cuando se tenga y el símbolo infinito cuando no exista tal valor. En un grafo ponderado se llama peso de un camino a la suma de los pesos de las aristas (o arcos) que lo forman.

Sea G=(V,A) un grafo ponderado finito tal que V={v¹, … , vⁿ}. Se llamará matriz de peso del grafo G a la siguiente matriz de orden n x n:

• En un grafo ponderado llamado camino más corto entre dos vértices dados al camino de peso mínimo entre dichos vértices.
• En un grafo ponderado se llamará camino más largo o camino critico entre dos vértices al camino de peso máximo entre dichos vértices.

Relaciones de adyacencia

Sea G=(V,A) un grafo.

Si (u,v)€A, se dice que el vértice v es adyacente al vértice u.

En un grafo no dirigido la relación es simétrica.