Informático

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Problemas y algoritmos sobre Grafos
Problemas, Algoritmos y Programaci´n o

14 de Septiembre de 2011

PAP

Grafos

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Men´ del d´ u ıa
1

2

3

4

Definiciones y estructuras Grafos ´ Arboles Camino m´ ınimo Breadth-firstsearch (BFS) Dijkstra Bellman-Ford Floyd-Warshall ´ Arbol generador m´ ınimo Prim Kruskal Problemas Cantidad de caminos Problemas en grafos impl´ ıcitos Problemas
PAP Grafos

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Grafos ´ Arboles

Estructura de datos

Repaso de estructuras de datos: Grafo ´ Arbol

PAP

Grafos

Definiciones y estructurasCamino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Grafos ´ Arboles

Grafos
Un grafo se define como la pareja (V , E ), de v´rtices (o nodos, o e puntitos) y ejes (o aristas, o rayitas, o flechitas), donde E ⊆ V × V. Se usan para modelar muchos problemas que involucran puntitos y rayitas. Se describen de alguna(s) de estas formas: Por las adyacencias de cada v´rtice e Por la definici´n: elconjunto de v´rtices y el conjunto de ejes. o e Impl´ ıcitamente, por otra estructura. En adelante, n es la cantidad de v´rtices (|V |) y m es la cantidad e de aristas (|E |).

PAP

Grafos

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Grafos ´ Arboles

Grafos - tipos
Hay muchas variantes de grafos: Dirigidos: (u, v ) y (v , u) son aristas distintas. Nodirigidos: (u, v ) y (v , u) son la misma arista. Multi-grafos: Puede haber varias aristas entre la misma pareja ordenada. Hay muchas propiedades sobre grafos: Con o sin ciclos (dirigidos o no dirigidos) Conexos o no conexos. Completos, vac´ triviales. ıos, Hamiltonianos, euclideanos, cactus, etc.

PAP

Grafos

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo ProblemasGrafos ´ Arboles

Grafos - definiciones

El vecindario de un v´rtice u, N(u), es el conjunto de v´rtices e e x tales que (u, x) es una arista del grafo. El grado de un v´rtice u, d(u), es el cardinal de su vecindario. e En un digrafo esto es el grado de salida de u. Un camino en un grafo es una secuencia de aristas donde el extremo final de una arista es el inicial de la siguiente arista. Unciclo en un grafo es un camino que empieza y termina en el mismo v´rtice. e

PAP

Grafos

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Grafos ´ Arboles

Grafos - por adyacencia

De cada v´rtice se describe su conjunto de vecinos: e Como una lista de vecinos (lista de adyacencia). Como un conjunto, arreglo u otro contenedor. Como un conjunto sobre bits(matriz de adyacencia). Recorrer los vecinos de un v´rtices es recorrer los elementos del e contenedor. Recorrer todas las aristas es recorrer todos los vecinos de todos los v´rtices. e

PAP

Grafos

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Grafos ´ Arboles

Grafos - por adyacencia

Costo de las operaciones seg´n la representaci´n: u o Operaci´n oLista de adyacencia Matriz de adyacencia ¿(u, v ) ∈ E ? O(min(d(u), d(v ))) O(1) Recorrer N(u) O(d(u)) O(n) O(n + m) O(n2 ) Recorrer E Memoria n + 2m n2

PAP

Grafos

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Grafos ´ Arboles

Grafos - por adyacencia
Por lista de adyacencia se puede almacenar de la siguiente forma:
vvint lady(n, vint()); #defineagregar(u, v) \ { lady[u].push_back(v); lady[v].push_back(u); }

Por matriz de adyacencia se puede almacenar de la siguiente forma:
vvint mady(n, vint(n, 0)); #define agregar(u, v) \ { mady[u][v]++; mady[v][u]++; }

PAP

Grafos

Definiciones y estructuras Camino m´ ınimo ´ Arbol generador m´ ınimo Problemas

Grafos ´ Arboles

Grafos - por definici´n o
Se describe el conjunto de...