GRAFOS
DEFINICIÓN
Un grafo G = (V, E) consiste en:
• Un conjunto de V nodos (vértices)
• V = {v1,…, vn}
• Un conjunto de E de aristas (arcos)
• E={e1,…,em}
Cada arista es un par (v,w) siendo v,w V
Si el par está ordenado, el grafo es dirigido
Se puede asociar a las aristas un tercer componente: coste(peso)
Ejemplo:
• G = (V,E)
• V = {a,b,c,d}
• E = {{a,b},{b,c},{a,c}, {a,d}, {d,b}}
2
Ejemplos
Red de vuelos
3
Ejemplo
Diagrama de flujo
4
Ejemplo
Arquitectura de redes
5
Ejemplo
Circuito eléctrico
6
TERMINOLOGÍA
Vértices adyacentes: unidos por un arco o arista
Grado de un vértice: número de vértices adyacentes a v,
calculado como deg(v) o deg(G,v)
Camino: secuencia de vértices, tal que dos vértices
consecutivos son adyacentes
Camino simple: aquel que no tiene vértices repetidos
Ciclo: camino simple, excepto que el último vértice es el
primero
Un grafo es conexo si entre dos nodos hay un camino
Un bosque es un grafo sin cilcos
7
PROPIEDADES
8
TIPOS DE GRAFOS
Grafos dirigidos: cuando se tiene una relación de orden en las
aristas
Las aristas son llamados arcos y se presentan como pares para
indicar el orden:
V = { a,b,c,d,e}
A ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),(c,b) }
9
TIPOS DE GRAFOS
Si los vértices de la arista son coincidentes se llaman auto-
bucles
Este caso se da en grafos no dirigidos
10
TIPOS DE GRAFOS
Si existen mas de una arista se llaman Multigrafos
11
TIPOS DE GRAFOS
En el caso de la aristas que contengan un valor numérico, al
grafo generado se llama Grafos Valorados. El valor asociado
es conocido como coste/peso
12
IMPLEMENTACIÓN
Matriz de adyacencia
Lista de adyacencia
13
MATRIZ DE ADYACENCIA
14
LISTAS DE ADYACENCIA
15
ARBOL DE EXPANSIÓN
Un árbol de expansión de un grafo G es un subgrafo G’ tal
que:
G’ es un árbol
G’ contiene todos los vértices de G
16
BÚSQUEDA
En profundidad
En anchura
17
BÚSQUEDA EN PROFUNDIDAD
18
BÚSQUED EN ANCHURA
19
PROBLEMA DEL CAMINO MÍNIMO
Encontrar el camino más corto desde un vértice O a
cualquier otro vértice
Consideramos grafos dirigidos
Variantes:
Sin pesos
Con pesos positivos
Con pesos (positivos y) negativos
Caso especial
Grafos dirigidos acíclicos
20
Camino mínimo sin pesos
Encontrar el camino más corto (medido por el número de
aristas) desde un vértice O a cualquier otro vértice
Estrategia: búsqueda en anchura
21
