unidad 2 grafos Árboles abarcadores mínimos caminos más cortos

UNIDAD 2Grafosrboles abarcadores mnimosCaminos ms cortos

Grafos

DefinicionesUn grafo G = (V, E) est formado por un conjunto de vrtices V y un conjunto de aristas EEn ocasiones las aristas se denominan arcos y los vrtices nodosLos grafos dirigidos se denominan digrafosUn grafo con costos en sus aristas se denomina grafo pesado

DefinicionesAlgunas situaciones que pueden representarse:Mapas de caminosDiagramas de circuitosCaminos ms cortosHorarios de clasePlaneacinRutas crticasOrden causal

RepresentacionesLa forma ms comn es por medio de un diagrama

Los vrtices se representan con crculos y las aristas con lneas dirigidas o no

EjemploV = {A, B, C, D, E}E = {e1, e2, e3, e4, e5, e6}G = {(A,D), (A,C), (D,C), (E,C), (E,B), (C,B)}

EjemploGrafo dirigido

RepresentacionesExisten diferentes estructuras de datos que pueden utilizarse para representar un grafoMatriz de adyacenciaLista de adyacencia

Las formas de representar a un grafo dirigido son las mismas

Matriz de adyacenciaSea un grafo G = (V, E), donde V ={0, 1, 2, 3, .., n}, se representa con una matriz de adyacencia M, tal que M es una matriz booleana de nxn, tal que M[i][j] es verdadero si existe una arista entre i y j, en caso contrario M[i][j] es falso

Ejemplo

Matriz de adyacencia

Matrices etiquetadas de adyacenciaSe utiliza para representar grafos pesadosLa representacin es similar pero el elemento [i][j] tiene el costo de la arista que va de i a jSi no existe un arco entre i y j se le asigna un valor especial a la entrada (generalmente infinito)

Ejemplo

Listas de adyacenciaEs una lista, en algn orden dado de todos los vrtices adyacentes a lPara representar un grafo se puede utilizar una lista o un arreglo donde cada al elemento i es una lista de adyacencia para el vrtice iPara representar un grafo con pesos se aade a cada nodo un nuevo dato con el peso de su arco

Ejemplo

RecorridosLos algoritmos ms conocidos para recorrer los nodos de un grafo son:Bsqueda primero en amplitudBsqueda primero en profundidad

Bsqueda en profundidadLa idea es visitar nuevos vrticesEl recorrido inicia en cualquier vrtice llamado la raz de la bsqueda que se marca como visitadoUn vrtice w adyacente a v, que no se encuentre marcado como visitado se empieza a recorrer recursivamente

EjemploSi el algoritmo inicia con el vrtice 1, el orden en que se visitan los nodos es:1, 2, 5, 4, 3, 7, 0, 6

Implementacin

Bsqueda en amplitudDado un nodo, se visita a todos sus vrtices adyacentes y posteriormente a los adyacentes de estos adyacentesSe puede ver como un recorrido en niveles, en el nivel 0 encontramos al vrtice inicial, en el 1 a sus adyacentes y as sucesivamente

Ejemplo

Ejemplo, contNivel 0: ANivel 1: B, F, ENivel 2: C, INivel 3: D, G, J, M, NNivel 4: H, L, KNivel 5: O, PEl recorrido podra quedar: A, B, F, E, C, I, D, G, J, M, N, H, L, K, O, P

Implementacin

Implementacin de un Grafo

Implementacin

Implementacin, Limpiar

Implementacin, Bsqueda en profundidad

Implementacin, Bsqueda en amplitud

rboles Abarcadores Mnimos (AAM)

DefinicionesUn rbol Abarcador de un grafo G es un sub-grafo de G que es un rbol y contiene a todos los vrtices de G Un rbol Abarcador Mnimo es un rbol abarcador con peso mnimoUn rbol abarcador mnimo de un grafo pesado es un conjunto de arcos que conectan a todos los vrtices del grafo en donde la suma de los pesos de los arcos es tan pequea como la suma de pesos de cualquier otro conjunto de arcos que conecten a todos los vrtices

DefinicionesSi el rbol no es conexo (que todos los vrtices estn conectados), no existe un rbol abarcadorUn rbol abarcador mnimo en un grafo G es un sub-grafo T de G que cumple con las siguientes propiedades:V = VT es conexoT es acclico

rbol abarcador mnimoPara encontrar un rbol abarcador mnimo dado un grafo G se tienen los siguientes algoritmos:Algoritmo de Prim/DijkstraAlgoritmo de Kruskal

Algoritmo de PrimSelecciona un vrtice arbitrario y se ramifica hacia fuera desde la parte construida seleccionando un nuevo vrticeLos vrtices pueden dividirse en tres categoras:Vrtices en el rbol construidoVrtices en el lmite o bordo, no estn en el rbol pero son adyacentes a algn vrtice en el rbolVrtices no visitados

Algoritmo de PrimLa idea es seleccionar un vrtice lmite y un arco incidenteEl algoritmo selecciona un arco de un vrtice del rbol o un vrtice lmite con peso mnimoDespus de cada iteracin, puede haber nuevos vrtices lmites

Ejemplo

Finalmente se debe obtener el costo del rbol abarcado mnimo

Costo = (A, B) + (A, G)+ (G, I) +(I, F) + (I, E) + (E, D) + (C, D) + (H, C)

Costo = 2 +3 +1 +5 +2 +1 +2 +2 = 18

Algoritmo de KruskalSe basa en aadir un arco a la vez

Utiliza el arco ms pequeo

Los arcos seleccionados no deben formar ciclos

JFKBOSMIAORDLAXDFWSFOBWIPVD867270418712588491447401391184946109011212342184662180214641235337

PVD867270418712588491447401391184946109011212342184662180214641235337

LAXDFWSFOBWIPVD867270418712588491447401391184946109011212342184662180214641235337

1447401391184946109011212342184662180214641235337

El costo es:(BOS, JFK) + (PVD, JFK) + (JFK, BWI) + (BWI, ORD) + (BWI, MIA) + (ORD, DFW) + (DFW, LAX) + (LAX, SFO) =187 + 144 + 184 + 946 + 621 + 802 + 1235 + 337 = 4456

Grafos dirigidos

DefinicionesEn los problemas de computacin y otras ciencias, a menudo es necesario representar relaciones arbitrarias entre objetos

Un grafo dirigido G consiste en un conjunto de vrtices V y un conjunto de aristas A

DefinicionesLos vrtices se denominan tambin nodos o puntos

Las aristas pueden denominarse arcos dirigidos

Una arista es un par ordenado de vrtices (v,w); v es la cola y w la cabeza de la arista

DefinicionesLa arista (v,w) se expresa a menudo como vw y se representa como:

Problemas de los caminos ms cortos

Problemas del camino ms cortoConsiste en encontrar un camino para llegar de manera ms rpida (menor costo sumando las aristas recorridas) de un vrtice origen a uno destino

Se pueden encontrar varia opciones de ste tipo de problemas:Camino ms corto con un solo origenCamino ms corto entre todos los nodos

Camino ms corto con un solo origenSuponer que se tiene un grafo dirigido G=(V,A) en el cual cada arista tiene una etiqueta no negativa, y donde un vrtice se especifica como origen

El problema es determinar el costo del camino ms corto del origen a todos los dems vrtices de V

Donde la longitud de un camino es la suma de los costos de las aristas del camino

Algortimo de DijkstraOpera a partir de un conjunto S de vrtices cuya distancia ms corta desde el origen ya es conocidaEn principio, S contiene slo el vrtice de origenEn cada paso, se agrega algn vrtice restante v a S, cuya distancia desde el origen es la ms corta posible

Ejemplo

Camino ms corto entre todos los parestil cuando se desea construir una tabla que brinde el menor costo para llegar de un punto a otro

Este es el problema del camino mnimo entre todos los pares (CMCP)

El problema consiste en encontrar el camino de longitud ms corta entre v y w para cada par ordenado de vrtices (v,w)

Algoritmo de R.W. FloydUsa una matriz A de n x n en la que se calculan las longitudes de los caminos ms cortos

Inicialmente A[i][j] = G[i][j] para toda i j

Se hacen n iteraciones a la matriz A, al final de la k-sima iteracin A[i][j] tendr por valor la longitud ms pequea de cualquier camino que vaya desde i a j y que no pase por un nmero mayor de k vrtices

Algoritmo de R.W. FloydEn la k-sima iteracin se aplica la siguiente frmula para calcular A

Ejemplo

Iteraciones

Implementacin

Cerradura transitivaVariante del algoritmo del algoritmo de Floyd

Conocido como el algoritmo de Warshall

Se utiliza para saber si existe un camino entre un par de nodos

Cerradura transitivaPuede obtenerse con un procedimiento similar al de Floyd aplicando la siguiente frmula en el k-simo paso en la matriz booleana A:

Ak[i][j] Ak-1[i][j] o (Ak-1 [i][k] & Ak-1[k][j])

Ejemplo

Cerradura transitiva

Implementacin

unidad 2 grafos Árboles abarcadores mínimos caminos más cortos

Documents