Teoría de Grafos Presentación PDF

10 2 1 2 2 b d 45 20 3...

10 2 1 2 2 b d 45 20 3 55 s 4 40 25 1 t 30 5 3 3 25 3 2 a c 50 15 4 Grafos ELGI. EUNICE SANTIAGO MANZANO MD II Índice general 1.1 Conceptos. 1.2 Clasificación. 1.3 Representación de estructuras. 1.4 Espacio de estados. 1.5 Algoritmos de recorrido y búsqueda. ELGI. EUNICE SANTIAGO MANZANO MD II Indice  Introducción.  Definiciones.  Tipo de dato abstracto grafo.  Estructuras de datos para grafos.  Lista de aristas.  Lista de adyacencia.  Matriz de adyacencia. ELGI. EUNICE SANTIAGO MANZANO MD II  Introducción  Los grafos se usan para modelar problemas definidos en términos de relaciones o conexiones entre objetos.  Tienen un amplio uso en ingeniería para representar redes de todo tipo:  transporte (tren, carretera, avión),  servicios (comunicación, eléctrica, gas, agua),  de actividades en el planeamiento de proyectos, etc. ELGI. EUNICE SANTIAGO MANZANO MD II  ¿Qué es un grafo?  Un grafo G = (V, E) está compuesto de: V : conjunto de vértices o nodos E : conjunto de aristas o arcos que conectan los vértices en V · Una arista e = (v, w) es un par de vértices · Ejemplo: a b V = { a, b, c, d, e} c E = { (a, b), (a, c), (a,d), (b, e), (c, d), (c, e), d ELGI. EUNICE SANTIAGO MANZANO MD II e (d, e) }  Aplicaciones · Grafo de transiciones (AFD) · Tiempo de vuelos aéreos b 2 2 b Santander Barcelona Coruña 2 1 inicio a b b 1 0 1 2 3 Madrid a 4 2 2 3 Valencia a a Sevilla · Planificación de tareas · Grafo asociado a un dibujo de (Pert/CPM) líneas (visión artificial) D(2) inicio A(3) I(1) C(4) E(3) final B(2) ELGI. EUNICE SANTIAGO MANZANO MD II  Definiciones  Arista dirigida: par ordenado (u, v) u v · Arista no dirigida: par no ordenado (u, v) u v · Grafo dirigido o digrafo: grafo cuyas aristas son todas dirigidas. · Grafo no dirigido o grafo: grafo cuyas aristas son todas no dirigidas. · Grafo mixto: grafo con aristas dirigidas y no dirigidas. ELGI. EUNICE SANTIAGO MANZANO MD II Matriz de Adyacencia ELGI. EUNICE SANTIAGO MANZANO MD II Representación de matriz de adyacencia ELGI. EUNICE SANTIAGO MANZANO MD II Representación de matriz de adyacencia ELGI. EUNICE SANTIAGO MANZANO MD II  Definiciones  Vértices adyacentes: vértices finales de una arista.  Un vértice w es adyacente a v sí y sólo si (v, w) (ó (w, v)) pertenece a E.  En grafos no dirigidos la relación de adyacencia es simétrica.  En grafos dirigidos la relación de adyacencia no es simétrica. a b Vértices adyacentes: a = { b, c, d } b={e} c c = { a, d, e } d = { a, c } d e ELGI. EUNICE SANTIAGO MANZANO MD II e={d}  Definiciones  Grado de un vértice v (grado(v)) en un grafo: número de aristas incidentes en v o número de vértices adyacentes.  En un digrafo:  Grado entrante de un vértice v (graent(v)): número de aristas entrantes a v.  Grado saliente de un vértice v (grasal(v)): número de aristas salientes de v.  Si G es un grafo con m aristas, entonces  grado (v ) 2 m vG  Si G es undigrafo graent ( v )con  m aristas, grasal ( v )  m entonces vG vG ELGI. EUNICE SANTIAGO MANZANO MD II  Definiciones  Sea G es un grafo con n vértices y m aristas.  Si G es no dirigido, entonces m  n(n-1)/2.  Si G es dirigido, entonces m  n(n-1).  Camino: secuencia de vértices tal que (vi, vi+1) son adyacentes. a b a b c c d e d e C1= { a, b, e, d, c} C2= { b, e, d, c} ELGI. EUNICE SANTIAGO MANZANO MD II Graficas bipartitas ELGI. EUNICE SANTIAGO MANZANO MD II Graficas bipartitas ELGI. EUNICE SANTIAGO MANZANO MD II ELGI. EUNICE SANTIAGO MANZANO MD II  Definiciones  Camino simple: todos los vértices son distintos.  Longitud de un camino: número de aristas del camino = n – 1.  Ciclo: camino simple que tiene el mismo vértice a inicial ybfinal. Camino simple = { a, b, e} c Ciclo = { c, e, d, c} d ELGI. EUNICE SANTIAGO MANZANO MD II e  Definiciones  Dos vértices v, w están conectados si existe un camino de v a w.  Grafo conectado (conexo): si hay un camino entre cualquier par de vértices.  Si es un grafo dirigido se llama fuertemente conexo. a b a b c c d e d e Conectado ELGI. EUNICE SANTIAGO MANZANO MD II No conectado  Definiciones  Subgrafo: subconjunto de vértices y aristas que forman un grafo.  Componente conectado: subgrafo conectado máximo. ELGI. EUNICE SANTIAGO MANZANO MD II 3 componentes conectados  Definiciones  Árbol: grafo conectado sin ciclos.  Bosque: colección de árboles.  Grafo completo: todos los pares de vértices son adyacentes. (m = n*(n-1)/2)  En un grafo no dirigido G con n vértices y m aristas se cumple lo siguiente:  Si G es conectado, entonces m  n - 1  Si G es un árbol, entonces m = n - 1  Si G es un bosque, entonces m  n - 1 ELGI. EUNICE SANTIAGO MANZANO MD II  Definiciones  Árbol de cubrimiento de un grafo G: subgrafo que  es un árbol.  contiene todos los vértices de G. El fallo de una arista desconecta el sistema (menos tolerante a fallos). ELGI. EUNICE SANTIAGO MANZANO MD II  Definiciones  Un grafo está etiquetado si asociamos a cada arista un peso o valor.  Grafo con pesos: grafo etiquetado con valores numéricos. 2 2 b d 3 s 4 1 t 3 3 2 a c ELGI. EUNICE SANTIAGO MANZANO MD II  Definiciones  Circuito de Euler: camino que recorre todas las aristas una vez y retorna al vértice de partida. C grafo A D Puentes de Koenigsberg B · Teorema de Euler (1736): un grafo tiene un circuito de Euler si y solo si todos los vértices tienen grado par. · Más definiciones y teoremas en Teoría de Grafos. ELGI. EUNICE SANTIAGO MANZANO MD II  El tipo de dato abstracto Grafo  El TDA Grafo es un contenedor de posiciones que almacena los vértices y las aristas del grafo.  Operaciones para la información posicional:  tamano(), devuelve el número de vértices más el número de aristas de G.  estaVacio()  elementos()  posiciones()  reemplazar(p, r)  intercambiar(p, q) donde p y q indican posiciones, y r indica un elemento de información. ELGI. EUNICE SANTIAGO MANZANO MD II  El tipo de dato abstracto Grafo  Operaciones generales: (v: vértice, e: arista, o: elemento de información). numVertices() Devuelve el número de vértices de G numAristas() Devuelve el número de aristas de G vertices() Devuelve una lista de los índices de los vértices de G aristas() Devuelve una lista de los índices de las aristas de G grado(v) Devuelve el grado de v verticesAdyacentes(v) Devuelve una lista de los vértices adyacentes a v aristasIncidentes(v) Devuelve una lista de las aristas incidentes en v verticesFinales(e) Devuelve un array de tamaño con los vértices finales de e opuesto(v, e) Devuelve los puntos extremos de la arista e diferente a v esAdyacente(v, w) Devuelve verdadero si los vértices v y w son ELGI. EUNICE SANTIAGO MANZANO MD II adyacentes  El tipo de dato abstracto Grafo  Operaciones con aristas dirigidas: aristasDirigidas() Devuelve una lista de todas las aristas dirigidas aristasNodirigidas() Devuelve una lista de todas las aristas no dirigidas gradoEnt(v) Devuelve el grado de entrada de v gradoSalida(v) Devuelve el grado de salida de v aristasIncidentesEnt(v) Devuelve una lista de todas las aristas de entrada a v aristasIncidentesSal(v) Devuelve una lista de todas las aristas de salida a v verticesAdyacentesEnt(v) Devuelve una lista de todas las aristas adyacentes a v a través de las aristas de entrada a v verticesAdyacentesSal(v) Devuelve una enumeración de todas las aristas adyacentes a v a través de las aristas de salida a v destino(e) Devuelve el destino de la arista dirigida e origen(e) Devuelve el origen de la arista dirigida e ELGI. EUNICE SANTIAGO MANZANO MD II esDirigida(e) Devuelve verdadero si la arista e es dirigida  El tipo de dato abstracto Grafo  Operaciones para actualizar grafos:  insertaArista(v, w, o) Inserta y devuelve una arista no dirigida entre los vértices v y w, almacenando el objeto o en esta posición  insertaAristaDirigida(v, w, o) Inserta y devuelve una arista dirigida entre los vértices v y w, almacenando el objeto o en esta posición  insertaVertice(o) Inserta y devuelve un nuevo vértice almacenando el objeto o en esta posición  eliminaVertice(v) Elimina vértice v y todas las aristas incidentes  eliminaArista(e) Elimina arista e  convierteNoDirigida(e) Convierte la arista e en no dirigida  invierteDireccion(e) Invierte la dirección de la arista dirigida e  asignaDireccionDesde(e, v) Produce arista dirigida e salga del vértice v ELGI.  EUNICE SANTIAGO MANZANO MD II asignaDireccionA(e, v) Produce arista dirigida e entrante al vértice v  Estructuras de datos para Grafos  Se necesita almacenar los vértices y las aristas del grafo y realizar eficientemente las operaciones del TDA Grafo.  Las estructuras de datos usuales son:  Lista de aristas.  Lista de adyacencia.  Matriz de adyacencia. ELGI. EUNICE SANTIAGO MANZANO MD II  Lista de Aristas  La estructura lista de aristas almacena los vértices y las aristas en secuencias sin ordenar.  Fácil de implementar.  Hallar las aristas incidentes sobre un determinado vértice es ineficiente porque requiere el examen entero de la estructura que almacena las aristas. a 1 2 a b c d e d e b 1 2 3 4 4 ELGI. EUNICE SANTIAGO MANZANO MD II c 3  Eficiencia de la estructura Lista de Aristas Operación Tiempo tamano, estaVacio, remplazarElemento, O(1) intercambiar numVertices, numAristas O(1) vertices O(n) aristas, aristasDirigidas, aristasNodirigidas O(m) elementos, posiciones O(n + m) verticesFinales, opuesto, origen, destino, O(1) esDirigida, grado, gradoEnt, gradoSalida aristasIncidentes, aristasIncidentesEnt, aristasIncidentesSal, verticesAdyacentes, O(m) verticesAdyacentesEnt, verticesdyacentesSal esAdyacente O(m) aristasIncidentes, aristasIncidentesEnt, aristasIncidentesSal, verticesAdyacentes, O(1) verticesAdyacentesEnt, verticesdyacentesSal insertaVertice O(1) eliminaVertice O(m) ELGI. EUNICE SANTIAGO MANZANO MD II Espacio requerido O(n + m)  Lista de Adyacencia  Lista de adyacencia del vértice v: secuencia de vértices adyacentes a v.  Representa el grafo por las listas de adyacencia de todos los vértices.  Es la estructura más usada para representar grafos con pocas aristas a (dispersos). 1 2 1 2 a 4 d e 2 3 b d b 3 4 c 4 2 e 4 ELGI. EUNICE SANTIAGO MANZANO MD II c 3 Eficiencia de la estructura Lista de Adyacencia Operación Tiempo tamano, estaVacio, remplazarElemento, O(1) intercambiar numVertices, numAristas O(1) vertices O(n) aristas, aristasDirigidas, aristasNodirigidas O(m) elementos, posiciones O(n + m) verticesFinales, opuesto, origen, destino, O(1) esDirigida, grado, gradoEnt, gradoSalida aristasIncidentes, aristasIncidentesEnt, aristasIncidentesSal, verticesAdyacentes, O(grado(v)) verticesAdyacentesEnt, verticesdyacentesSal esAdyacente O(min(grado(u), grado(v)) aristasIncidentes, aristasIncidentesEnt, aristasIncidentesSal, verticesAdyacentes, O(1) verticesAdyacentesEnt, verticesdyacentesSal insertaVertice O(1) eliminaVertice O(grado(v)) ELGI. EUNICE SANTIAGO MANZANO MD II Espacio requerido O(n + m)  Matriz de Adyacencia  Matriz M[i][j] con entradas para todos los pares de vértices.  En grafos no etiquetados:  M[i][j] = verdadero, si hay una arista (i, j) en el grafo.  M[i][j] = falso, si no hay una arista (i, j) en el grafo.  En grafos no dirigidos: M[i][j] = M[j][i]. La matriz es simétrica. 1 2 1 2 3 4 1 F V F V 2 V F V V 3 F V F V 4 V V V F 4 ELGI. EUNICE SANTIAGO MANZANO MD II 3  Matriz de Adyacencia  En grafos etiquetados:  M[i][j] = atributo de la arista (i, j) en el grafo, indicador especial si no hay una arista (i, j).  Es la estructura más usada para representar grafos con muchas aristas (densos). a 1 2 1 2 3 4 1 - a - d d e b 2 - - b - 3 - - - c 4 - e - - 4 ELGI. EUNICE SANTIAGO MANZANO MD II c 3 Eficiencia de la estructura Matriz de Adyacencia Operación Tiempo tamano, estaVacio, remplazarElemento, O(1) intercambiar numVertices, numAristas O(1) vertices O(n) aristas, aristasDirigidas, aristasNodirigidas O(m) elementos, posiciones O(n + m) verticesFinales, opuesto, origen, destino, O(1) esDirigida, grado, gradoEnt, gradoSalida aristasIncidentes, aristasIncidentesEnt, aristasIncidentesSal, verticesAdyacentes, O(n) verticesAdyacentesEnt, verticesdyacentesSal esAdyacente O(1) aristasIncidentes, aristasIncidentesEnt, aristasIncidentesSal, verticesAdyacentes, O(1) verticesAdyacentesEnt, verticesdyacentesSal insertaVertice O(n2) eliminaVertice O(n2) ELGI. EUNICE SANTIAGO MANZANO MD II Espacio requerido O(n2)