Multígrafos

Sea G = (V, E) un grafo dirigido, donde V es un conjunto y E es un multiconjunto de pares ordenados de V  V. G es llamado un multigrafo dirigido y geométricamente puede representarse como un conjunto de vértices V y un conjunto de flechas E entre los vértices, donde no existe restricción en el numero de flechas de un vértice a otro.

Multigrafo Dirigido

Ahora consideremos una representación gráfica de un mapa de carreteras en el cual una arista entre dos ciudades corresponde a un carril en una autopista entre las dos ciudades. Como a menudo hay autopistas de varios carriles entre pares de ciudades, esta representación origina un multigrafo.

La noción de multigrafo no dirigido puede definirse de manera similar a la de un multigrafo dirigido.

Multigrafo No Dirigido

Definición:
Un grafo ponderado (o grafo con peso) es un grafo en el cual hay datos asociados a sus lados, el valor w(i, j) esta asociado con el lado (i, j) y se llama ponderación o peso del lado (i, j).
Definición:
Eel peso o ponderación de un grafo es la suma de los pesos de sus lados. Frecuentemente el peso de un camino se le conoce como longitud del camino.
Ejemplo: 
Si se interpretan las ciudades como vértices y los caminos entre ellas como sus lados, al asignarles un valor a sus caminos resulta un grafo ponderado o con peso.

Grafo Ponderado