Grafos

Exploración de grafos
Análisis y Diseño de Algoritmos

Exploración de grafos
Grafos Recorridos sobre grafos
Búsqueda primero en profundidad Búsqueda primero en anchura

Backtracking (“vuelta atrás”)
Descripción general Espacio de soluciones Implementación Ejemplos

Branch & Bound (“ramificación y poda”)
Descripción general Estrategias de ramificación Implementación Ejemplos

1Grafos
Grafo G = (V,E) V: Conjunto de vértices o nodos del grafo. E ⊆ VxV: Conjunto de aristas o arcos. VxV: Tipos de grafos Grafos no dirigidos Aristas (no orientadas). dirigidos: (v,w) = (w,v) v,w) (w,v) v w

Grafos dirigidos: Arcos (con dirección). dirigidos: (v,w) ≠ (w,v) v,w) w,v) v w
2

Grafos
Ejemplo: US Biotech Industry

3

Grafos - Definiciones
Grafos no dirigidos Grado de unvértice: Número de aristas que lo contienen. Grafos dirigidos Grado de salida de un vértice v: Número de arcos cuyo vértice inicial es v. Grado de entrada de un vértice v: Número de arcos cuyo vértice final es v.

4

Grafos - Definiciones
Nodos/vértices adyacentes: adyacentes: Vértices conectados por una arista (o un arco). v w

Aristas/arcos adyacentes: adyacentes: Arcos/aristas con unvértice común. u v w

Bucle: Arco/arista cuyos vértices inicial y final coinciden. v
5

Grafos - Definiciones
Camino [path]: path]: Sucesión de arcos adyacentes tal que el vértice final de cada arco coincide con el inicial del siguiente. Secuencia (w1, w2, ..., wk)∈ V tal que (w1, w2), (w2, w3), ..., (wk-1, wk) ∈ E. Longitud del camino: camino: Número de arcos del camino (k-1). (kCircuito (ociclo): Camino que empieza y acaba en el mismo vértice.

6

Grafos - Definiciones
Grafo conexo: conexo: Un grafo no dirigido es un grafo conexo si para todo par de nodos u y v existe una camido de u a v. Componentes conexas: conexas: Cada uno de los conjuntos maximales conexos.

7

Grafos - Definiciones
Tipos de grafos Grafo etiquetado: etiquetado: Cada arista y/o vértice tiene asociada unaetiqueta/valor. Grafo ponderado = Grafo con pesos: Grafo etiquetado en el que existe un valor numérico asociado a cada arista o arco. Multigrafo: Multigrafo: Grafo en el que se permite que entre dos vértices exista más de una arista o arco.
8

Grafos - Definiciones
Árbol: Árbol: Grafo conexo que no contiene ciclos. Teorema Sea G un grafo de n nodos. Cualquier pareja de las siguientesafirmaciones implica la tercera: G es conexo. G no contiene ciclos. G tiene n-1 aristas. n9

Grafos - Representación
Representación mediante matrices de adyacencia
1 2 3 4 5 6 7 8 1 0 1 1 0 0 0 0 0 2 1 0 1 1 1 0 0 0 3 1 1 0 0 1 0 1 1 4 0 1 0 1 1 0 0 0 5 0 1 1 1 0 1 0 0 6 0 0 0 0 1 0 0 0 7 0 0 1 0 0 0 0 1 8 0 0 1 0 0 0 1 0

Matriz de adyacencia de tamaño |V|x|V| V|x|V| A[u][v] = 1 si (u, v) ∈ E.A[u][v] = 0 si (u, v) ∉ E.
10

Grafos - Representación
Representación mediante matrices de adyacencia Ventaja: Acceso eficiente a una arista, Θ(1). Inconvenientes: Θ(|V|2) en identificar todas las aristas. aristas. Espacio proporcional a |V|2 (se desperdicia memoria si el grafo es poco denso). (s

11

Grafos - Representación
Representación mediante listas de adyacencia
1 2 3 4 5 6 7 8 2 11 2 2 5 3 3 8 7 3 3 2 5 3 4 6 4 5 5 7 8

Array de listas enlazadas de nodos adyacentes.

12

Grafos - Representación
Representación mediante listas de adyacencia Ventajas: Espacio proporcional a |V|+|E|. (representación adecuada para grafos poco densos). Θ(|V|+|E|) en identificar todas las aristas. Inconvenientes: Se tarda O(grado(u)) en comprobar si (u,v)∈E. Ineficiente para encontrar losarcos que llegan a un nodo (solución: usar estructuras de listas múltiples).
13

Recorridos sobre grafos
Se parte de un nodo dado y se visitan los vértices del grafo de manera ordenada y sistemática, pasando de un vértice a otro a través de las aristas del grafo. Tipos de recorridos: Búsqueda primero en profundidad: Equivalente al recorrido en preorden de un árbol. Búsqueda primero en...