Embed Size (px)
Citation preview
Oscar Bedoya.
http://eisc.univalle.edu.co/~oscarbed/Estructuras/
Edificio 331, 2º piso, E.I.S.C.
Estructuras de datos y Estructuras de datos y algoritmosalgoritmos
Grafos
Lo grafos son estructuras de datos, utilizadas comúnmente en el manejo de redes, en la construcción de circuitos eléctricos, en la estrategia de ventas y en muchas otras áreas del conocimiento
Grafos
Un grafo es una estructura de datos compuesta por vértices y arcos
•V = {A, B, C, D, E}
•Un arco une dos vértices adyacentes
A
B
C
D
E
Grafos
Grafo dirigido o Digrafo
Es un grafo en el que los arcos tienen una orientación
A
B
C
D
E
Grafos
Incidencia de los arcos
Un arco es incidente en un vértice, si una de sus puntas llega a ese vértice
A
B
C
D
E
Grafos
Incidencia de los arcos
Un arco es incidente en un vértice, si una de sus puntas llega a ese vértice
A
B
C
D
E
Grafos
Grafos y digrafos fuertemente conectados
Un grafo está fuertemente conectado si desde cualquier vértice se puede llegar a todos los demás
A B
C D
E
Grafos
Grafos y digrafos débilmente conectados
Un grafo está débilmente conectado, si por lo menos desde un vértice no se puede llegar a los demos
A B
C D
E
Grafos
Grafo Euleriano
Un grafo es Euleriano si partiendo de algún vértice, se pueden recorrer todos los arcos llegando de nuevo al vértice de origen.
Se pueden visitar los vértices cuantas veces sea necesario, pero los arcos se pueden repetir solo una vez
A
B C D
EF
G
H
Grafos
Grafo Euleriano
D
EF
Grafos
Grafo Euleriano
D
EF
A
Grafos
Grafo Euleriano
C D
EF
Grafos
Grafo Euleriano
C D
EF
A
Grafos
Grafo Hamiltoniano
Un grafo es Hamiltoniano si partiendo de algún vértice se pueden recorrer todos los vértices sin repetir ninguno y finalmente se puede llegar al vértice de origen. Los arcos se pueden recorrer una o mas veces
A
B C D
EF
G
H
Grafos
Grado de un vértice
El grado de un vértice es el número de arcos que inciden en ese vértice
El grado de A es 2
El grado de G es 4
A
B C D
EF
G
H
Grafos
Grado de un vértice
En un digrafo se considera el grado de entrada y el grado de salida
A B
C D
E
Grafos
Grafos rectangulares
Un grafo es rectangular si todos los vértices tienen el mismo grado
B C
FH
Grafos
Arco cíclico
Un arco es cíclico si parte de un vértice y llega al mismo vértice
B C
FH
Grafos
Grafos completos
Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértices que componen el grafo
Grafos
Cómo almacenar la información de un grafo
•Lista de adyacencia
•Matriz de adyacencia
Grafos
•Lista de adyacencia
A
B
C
D
E
AA
BB
CC
DD
EE
grafoBB
AA
CC
CC
AA BB DD
CC EE
DD
Grafos
•Matriz de adyacencia
A
B
C
D
E
00 11 11 00 00
11 00 11 00 00
11 11 00 11 00
00 00 11 00 11
00 00 00 11 00
A B C D E
A
B
C
D
E
Grafos
A
B C D
EF
G
H
Grafos
Matriz de caminos1 2 3
4
56
8
7
9 10
Grafos
Matriz de caminos
11 22 33 44 55 66 77 88 99 1010
11 00 11 00 11 11 00 00 00 11 00
22 11 00 11 00 00 11 00 00 00 00
33 00 11 00 00 00 00 11 11 00 00
44 11 00 00 00 00 00 00 00 00 00
55 11 00 00 00 00 11 00 00 00 00
66 00 11 00 00 11 00 00 00 11 00
77 00 00 11 00 00 00 00 00 00 00
88 00 00 11 00 00 00 00 00 00 11
99 11 00 00 00 00 11 00 00 00 11
1010 00 00 00 00 00 00 00 11 11 00
Grafos
Matriz de caminos
La matriz de adyacencia indica cuántos caminos de longitud 1 se dan para cada vértice
Cómo determinar la cantidad de caminos de longitud 2
Grafos
Matriz de caminos
Para determinar la cantidad de caminos de longitud 2 se calcula M2, donde M es la matriz de adyacencia
Grafos
Matriz de caminos
La matriz de caminos
S= M + M1 + M2 + . . . + Mnv-1
permite conocer si existe un camino (sin importar la longitud) entre cada par de vértices
Cómo es S en un grafo fuertemente conectado
Grafos
Si cada punto representa una ciudad
•Existe un camino directo entre C1 y C4
•Existe un camino directo entre C4 y C6
•Cuántas formas existen de llegar de C1 a C7
C1
C2
C3
C4
C5
C6
C7C8
Grafos
Si cada punto representa una ciudad, cuál sería el camino más corto entre C2 y C7
C1
C2
C3
C4
C5
C6
C7C8
5
2
1
11
7
4
2
8
40
Grafos
Si cada punto representa una ciudad
•Existe un camino entre C1 y C4
•Existe un camino entre C2 y C1
•Existe un camino entre C2 y C7
C1
C2
C3
C4
C5
C6
C7C8
