Prueba

Tema 10- Grafos
1. 2. 3. 4. 5. 6. Duración: 2 semanas aprox. Índice general: Relaciones entre los Datos de una Colección Conceptos básicos sobre Grafos Representación de un Grafo: Matriz y Listas de Adyacencia Implementación de un Grafo en Java: las clases Arista, Vertice y Grafo Recorrido de un Grafo: ampliación de la clase Grafo Caminos Mínimos en un Grafo sin y con Pesos (Dijkstra): la claseJava CaminosDelGrafo

1

Objetivos:
Estudio de la Representación de una Relación Binaria entre los Datos de una Colección mediante la estructura Grafo y algunas de sus aplicaciones más significativas. Ello permitirá recapitular y ampliar conceptos y estructuras que se han estudiado a lo largo del curso, como:
la ventaja de re-utilizar el Software que presenta la POO, al estudiar las posiblesRepresentaciones de un Grafo (Modelos Diccionario y Lista Con Punto de Interés ) y la implementación de las operaciones de Recorrido y cálculo de caminos mínimos sobre él (Modelos Cola y Cola de Prioridad) las características de las Representaciones Lineal, Jerárquica y No Lineal de los Datos de una Colección para, respectivamente, su Acceso Secuencial, su Recorrido en Profundidad y Anchura y laBúsqueda Dinámica

Implementación en Java de un Grafo, que supondrá el diseño de las clases Arista, Vertice, Grafo y CaminosDelGrafo (ubicadas en el paquete grafos de estructurasDeDatos)

1

Bibliografía básica:

Weiss, M.A. Estructuras de datos en Java. Adisson-Wesley, 2000.
• •

Capítulo 14, para conceptos sobre Grafos y Grafos Dirigidos Capítulo 22, apartado 22.2.3 para el algoritmode Dijkstra con Montículos de Emparejamiento

Aho A.V., Hopcroft J.E., Ullman J.E. Estructuras de datos y Algoritmos. Addison-Wesley, 1988. Capítulo 6 para conceptos sobre Grafos y Grafos Dirigidos

3

Relaciones entre los Datos de la Colección
35 10

1) Representación Lineal 2) Representación Jerárquica

Sea un Colección cuyos Datos son: • ciudades • aeropuertos • computadores de unared • puntos del plano de una ciudad Queremos modelar • rutas entre ciudades • rutas aéreas • envío de correo electrónico • recorridos turísticos

• • • •

carreteras vuelos enlaces calles

4

2

Relaciones entre los Datos de la Colección

35

Relación Binaria entre los Datos de la Colección

10

3) Grafo cuyos Vértices se Relacionan vía Aristas

Una Relación R sobre unConjunto S se define como un Conjunto de Pares (a, b): a, b ∈ S si (a, b) ∈ R se escribe a R b y denota que a está Relacionado con b indica si cada Par de Datos del Conjunto están o no Relacionados
5

Conceptos básicos sobre Grafos Grafos Dirigidos y no Dirigidos Grafos Etiquetados Relaciones de Incidencia y Adyacencia Caminos

6

3

Conceptos básicos sobre Grafos: Grafos Dirigidos (Digrafos)Un Grafo Dirigido (gd) es un Par G = (V,E) V es un conjunto finito de Vértices (o Nodos o Puntos) E es un conjunto de Aristas (o Arcos) dirigidas Arista: Par ordenado de Vértices (u,v): u → v
1 4 2 5 3 6

7

Conceptos básicos sobre Grafos: Grafos no Dirigidos (Grafos)
Un Grafo no Dirigido (gnd) es un Par G = (V,E) V es un conjunto finito de Vértices E es un conjunto de Aristas no DirigidasArista: Par no ordenado de Vértices (u,v) = (v,u), u≠v : u  v
1 4 2 5 3 6

8

4

Conceptos básicos sobre Grafos: Grafos Etiquetados
Un Grafo Etiquetado es un grafo G = (V,E) sobre el que se define una función f: E → A, dónde A es un conjunto cuyas componentes se llaman Etiquetas NOTA: la función de etiquetado se puede definir también sobre V, el conjunto de Vértices Un Grafo Ponderado esun Grafo Etiquetado (sus Aristas) con números Reales (A ≡ ℜ) Ejemplos: discútase la necesidad de etiquetar/ponderar los Grafos asociados a las aplicaciones reseñadas en el primer punto del tema

9

Conceptos básicos sobre Grafos: Relaciones de Incidencia
Sea G = (V,E) un Grafo Dirigido. Si (u,v) ∈ E, decimos que Incide desde u (sale de ..) e Incide en v (llega a ..)
1 4 2 5 3 6

Sea G =...