Estructuras de datos y algoritmos
Oscar Bedoya.
[email protected]
http://eisc.univalle.edu.co/~oscarbed/Estructuras/
Edificio 331, 2º piso, E.I.S.C.
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
E
B
Un grafo es una estructura de datos
compuesta por vértices y arcos
A
D
•V = {A, B, C, D, E}
C
•Un arco une dos vértices
adyacentes
Grafos
E
Grafo dirigido o Digrafo
B
Es un grafo en el que los arcos tienen
una orientación
A
D
C
Grafos
E
Incidencia de los arcos
B
Un arco es incidente en un vértice, si
una de sus puntas llega a ese vértice
A
D
C
Grafos
E
Incidencia de los arcos
B
Un arco es incidente en un vértice, si
una de sus puntas llega a ese vértice
A
D
C
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
E
C
D
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
E
C
D
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.
B
D
F
E
G
A
H
Se pueden visitar los vértices cuantas
veces sea necesario, pero los arcos se
pueden repetir solo una vez
C
Grafos
Grafo Euleriano
D
F
E
Grafos
Grafo Euleriano
A
F
D
E
Grafos
Grafo Euleriano
C
D
F
E
Grafos
Grafo Euleriano
A
C
D
F
E
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
B
C
D
F
E
G
A
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
B
C
D
F
E
G
El grado de A es 2
El grado de G es 4
A
H
Grafos
Grado de un vértice
A
B
En un digrafo se considera el grado
de entrada y el grado de salida
E
C
D
Grafos
Grafos rectangulares
Un grafo es rectangular si todos los
vértices tienen el mismo grado
B
C
H
F
Grafos
Arco cíclico
Un arco es cíclico si parte de un
vértice y llega al mismo vértice
B
C
H
F
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
E
•Lista de adyacencia
B
A
grafo
B
C
B
A
C
C
A
B
D
C
E
E
D
A
D
D
C
Grafos
E
•Matriz de adyacencia
B
A
A
0
B
C
1
1
D
0
E
0
B
1
0
1
0
0
C
1
1
0
1
0
D
0
0
1
0
1
E
0
0
0
1
0
A
D
C
Grafos
B
C
D
F
E
G
A
H
Grafos
Matriz de caminos
1
2
3
4
8
6
7
5
9
10
Grafos
Matriz de caminos
1
2
3
4
5
6
7
8
9
10
1
0
1
0
1
1
0
0
0
1
0
2
1
0
1
0
0
1
0
0
0
0
3
0
1
0
0
0
0
1
1
0
0
4
1
0
0
0
0
0
0
0
0
0
5
1
0
0
0
0
1
0
0
0
0
6
0
1
0
0
1
0
0
0
1
0
7
0
0
1
0
0
0
0
0
0
0
8
0
0
1
0
0
0
0
0
0
1
9
1
0
0
0
0
1
0
0
0
1
10
0
0
0
0
0
0
0
1
1
0
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
C2
C5
C7
C1
C4
C3
C6
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
C8
Grafos
C2
C5
5
C1
11
C7
4
8
2
C3
C8
2
C4
1
40
7
C6
Si cada punto representa una ciudad, cuál sería el camino más
corto entre C2 y C7
Grafos
C2
C5
C7
C1
C4
C3
C6
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
C8
Descargar

Grafos