s3 2 grafos ponderados resized

7/25/2019 S3 2 Grafos Ponderados Resized

1/12

3.2 Grafos ponderados

Aplicaciones de laTeora de Grafosa la vida real

Alberto Conejero y Cristina Jordn

Depto. Matemtica Aplicada

E.T.S. Ingeniera Informtica

Universitat Politcnica de Valncia


2/12

Clculo de caminos

3.2. Grafos ponderados

Aplicaciones de la Teora de Grafos a la vida real

http://maps.google.es

Consideremos un mapa con varias ciudades y las distancias entre ellas (en km o min).

Cul es la ruta ms corta entre dos ciudades?


3/12

Grafo ponderado



Sea G un grafo G=(V,E), |V|=n

Se dice que G esponderado, si cada arista (respect. arco) (vi,vj)tiene un valorasociado, p(vi,vj), al que se llama peso o coste.

Los valores de un grafo ponderado habitualmente se presentan en forma de matriz.

Se puede definir una matriz similar a la de adyacencia donde reflejemos el valor delos pesos.

En general, asignaremos a los pesos cantidades que sean enteros no negativos.


4/12

Matriz de pesos

Los elementos de la matriz P se suelendenotar pi.jo pij.

Con pi.jse representa el elemento de lamatriz Pque se encuentra en la fila iy enla columnaj.

P=

p1,1

p1,2

... p1,n1 p1,n

p2,1

p2,2

... p2,n1 p2,n

.

.

.

.

.

....

.

.

.

.

.

.

pn1,1 pn1,2 ... pn1,n1 pn1,n

pn,1 an2 ... pn,n1 pnn

Sea G un grafo G=(V,E), |V|=n

Llamamosmatriz de pesosomatriz de costesde G a la matriz nxn P=(pi.j)cuyoselementos vienen definidos como sigue:




5/12

Consideremos el siguiente grafo

0 3

0 5

1 0 4

7 0 3

3 1 0

Ejemplo

v2

v3

v4

v5

v1

3

35

2

1

4

7

3




6/12

Clculo de caminos

Vamos a modelizar un mapa con 5 ciudades: Albacete, Alicante, Crdoba, Madrid yValencia. Estas ciudades estn conectadas en tren con la siguiente duracin enminutos:

Albacete-Madrid 100Albacete-Alicante 96Albacete-Crdoba 254Albacete-Valencia 105Alicante-Valencia 110Crdoba-Madrid 102Madrid-Valencia 98

Las conexiones son enambos sentidos con igualduracin

V={Ciudades}E={Pares de ciudades

conectadas entre s}P= Matriz con lasduraciones de lasconexiones entre pares deciudades.




7/12

Clculo de caminos

0 96 254 100 105

96 0 110

254 0 102

100 102 0 98

105 110 98 0









8/12

Clculo de caminos

0 96 254 100 105

96 0 110

254 0 102

100 102 0 98

105 110 98 0

Crdoba

Madrid

Madrid

Crdoba









9/12

Peso de un camino



Se puede definir una matriz similar a la de adyacencia donde reflejemos el valor delos pesos.

Sea G un grafo ponderado G=(V,E), |V|=n con P=(pi.j)como matriz de pesos.

Dado un camino en G definimos elpesoocoste del caminode

G a la matriz nxn P=(pi.j)cuyos elementos vienen definidos como sigue:

(vi1 ,vi2 ,...,vik)

(vi1 ,vi2 )+

(vi2 ,vi3 )+

(vi3 ,vi4 )+

...+

p(vik1 ,vik)


10/12

Consideremos el camino (v3,v4,v5,v1) en el siguiente grafo:

Ejemplo

v2

v3

v4

v5

v1

3

35

2

1

4

7

3 0 3

0 5

1 0 4

7 0 3

3 1 0

p(v3,v4)+p(v4,v5)+p(v5,v1) = 4 + 3 + 3 = 10




11/12

Clculo del peso de un camino

0 96 254 100 105

96 0 110

254 0 102

100 102 0 98

105 110 98 0

Supongamos que realizamos el siguiente viaje: Alicante, Valencia, Madrid, Crdoba.

Cul es la duracin del

mismo?




12/12

Clculo del peso de un camino

0 96 254 100 105

96 0 110

254 0 102

100 102 0 98

105 110 98 0

Supongamos que realizamos el siguiente viaje: Alicante, Valencia, Madrid, Crdoba.

Cul es la duracin del

mismo?

p( Alicante,Valencia) + p( Valencia, Madrid)+ p( Madrid, Crdoba) =p(2,5) + p(5,4) + p(4,3) = 110 + 98 + 102 = 310 min.

La solucin es la longitud del camino que pasa por los vrtices asociados a dichas

ciudades, es decir el camino que pasa por los vrtices 2,5,4 y 3. Por tanto, dichalongitud ser:



s3 2 grafos ponderados resized

Documents