Geafos Ponderados

Presentación

Grafos Ponderados

La presentación ha sido elaborada en base
al libro:

Almacenamiento y recuperación
de información

Las imágenes han sido tomadas de:
Las tablas han sidoelaboradas por:
José Manuel Varela Bonilla

La presentación ha sido elaborada por:

Dra. Beatriz Adriana González Beltrán
Departamento de Sistemas
UAM-Azcapotzalco
Trimestre 07P

Dra. BeatrizAdriana González Beltrán

Dra. Beatriz Adriana González
Beltrán. ARI - 07P.

Grafos ponderados

Grafos ponderados
Los grafos ponderados resuelven dos
tipos de problemas:

Asociar a lasaristas pesos o costes.
Casos:
rutas aéreas: distancias o tarifas
circuito eléctrico: conexiones cuyos pesos
son la logitud o precio de cables
proyecto: coste de realización de tareas,
tiempo.
Dra.Beatriz Adriana González
Beltrán. ARI - 07P.

3

Representación de grafos
ponderados

1.

2.

Encontrar la forma de conectar todos los puntos
al menor coste (árbol de expansión mínimo).Encontrar el camino de menor coste entre dos
puntos dados (el problema del camino más
corto).
Dra. Beatriz Adriana González
Beltrán. ARI - 07P.

4

Árbol de expansión mínimo

Representaciónpor matriz de adyacencia
La matriz puede contener pesos de aristas en
lugar de valores lógicos.

Representación por listas de adyacencia
Añadir un campo a cada elemento de la lista, a
manera depeso.
Se supone que todos los pesos son positivos.
Dra. Beatriz Adriana González
Beltrán. ARI - 07P.

2

5

Colección de aristas que conectan todos
los vértices y en el que la suma de lospesos de las aristas es al menos inferior
a la suma de los pesos de cualquier otra
colección de aristas que conecten todos
los vértices.

Dra. Beatriz Adriana González
Beltrán. ARI - 07P.

61

Propiedades de los grafos
ponderados

Propiedades de los grafos
ponderados

Dada una división cualquiera de los vértices
de un grafo en dos conjuntos, el árbol de
expansión mínimo...