Principios de Computadoras II
Grafos
Departamento de Ingeniería Electrónica y ComputadorasUniversidad Nacional del Sur
Ricardo [email protected]
Principios de Computadoras IIGrafosRicardo Coppo
2Universidad Nacional del Sur
Definición conceptual� Un grafo G = ( V, A ) es una estructura que
posee un conjunto de vértices V y un conjunto de aristas A.
� Una arista es un par de vértices (u,v). Las aristas también se conocen como arcos.
� Si el par (u,v) es ordenado, entonces el grafo es dirgido.
Principios de Computadoras IIGrafosRicardo Coppo
3Universidad Nacional del Sur
Ejemplo gráfico
a
b
c
d
e
f
Grafo no dirigidoV = { a, b, c, d, e, f }A = { (a,b), (a,c), (b,d), (c,d), (d,e), (b,f), (d,f) }
bd
a ce
f
Grafo dirigidoV = { a, b, c, d, e, f }A = { (a,b), (b,c), (b,d), (c,e), (d,e), (e,f) }
Principios de Computadoras IIGrafosRicardo Coppo
4Universidad Nacional del Sur
Ejemplos � Correlativas de materias para un plan de
estudios
� Esquema de conexión de una red de computadoras
� Red vial de una municipalidad
Principios de Computadoras IIGrafosRicardo Coppo
5Universidad Nacional del Sur
Grafos ponderados� Un grafo ponderado es aquel a la que se le
asigna un “costo” o valor a cada arista.
a
b
c
d
e
f
4 3
2
7
9
2
Principios de Computadoras IIGrafosRicardo Coppo
6Universidad Nacional del Sur
Grafos ponderados� Esquema de un circuito electrónico con
impedancias
� Workflow de un proceso de fabricación (cada vértice es un hito del proyecto y cada arista un proceso). Cada proceso se desarrolla en t días.
� Redes de computadoras ponderados por costo de transmisión de cada paquete ($ o velocidad)
Principios de Computadoras IIGrafosRicardo Coppo
7Universidad Nacional del Sur
Definiciones� Un vértice w es adyacente a v si y solo si
(w,v) es una arista del grafo.
� Observar que si el grafo es dirigido� (w,v) # (v,w)
v w
v
w
v es adyacente de ww es adyacente de v
v es adyacente de w
Principios de Computadoras IIGrafosRicardo Coppo
8Universidad Nacional del Sur
Definiciones� Un camino en un grafo es una secuencia de
vértices w1,w2,w3,…, wn si existen las aristas que (w1,w2), (w2,w3) … (wn-1, wn)
� La longitud de un camino es el número de aristas que el mismo posee. (n-1)
v vLongitud 0 Longitud 1
Principios de Computadoras IIGrafosRicardo Coppo
9Universidad Nacional del Sur
Definiciones� Un camino es simple si todos los vértices son
distintos con excepción del primero y del último que podrían ser el mismo.
� Un ciclo es un camino que nace y termina en el mismo vértice y cuya longitud mínima es 1.
� Un ciclo es simple si el camino que lo define es simple.
Principios de Computadoras IIGrafosRicardo Coppo
10Universidad Nacional del Sur
Ejemplos
a
b
c
d
e
f
Ciclo simple
a
b
c
d
e
f
Ciclo no simple
Principios de Computadoras IIGrafosRicardo Coppo
11Universidad Nacional del Sur
Definiciones� Un grafo es acíclico si no presenta ningún ciclo
� Un grafo no dirigido es conexo si hay un camino desde cualquier vértice a cualquier otro
� Si el grafo es dirigido y presenta esta propiedad se dice que es fuertemente conexo. Si solo es conexo el subgrafo no dirigido subyacente se dice que es débilmente conexo
Principios de Computadoras IIGrafosRicardo Coppo
12Universidad Nacional del Sur
Ejemplos
A
B C D E
F G I JH
K
Grafo acíclico
Principios de Computadoras IIGrafosRicardo Coppo
13Universidad Nacional del Sur
Ejemplos
bd
a ce
f
bd
a ce
f
Fuertemente conexo Débilmente conexo
Principios de Computadoras IIGrafosRicardo Coppo
14Universidad Nacional del Sur
Formas de representación� ¿Cómo introducir y almacenar en la memoria
de la computadora una estructura gráfica?
� Matriz de adyacencia
� Lista de adyacencia
Principios de Computadoras IIGrafosRicardo Coppo
15Universidad Nacional del Sur
Matriz de adyacencia
1
3 4
25
1 2 3 4 5
1 1 1 1 0 0
2 1 1 1 0 1
3 1 1 1 1 0
4 0 0 1 1 1
5 0 1 0 1 1
Principios de Computadoras IIGrafosRicardo Coppo
16Universidad Nacional del Sur
Matriz de adyacencia
1
3 4
25
1 2 3 4 5
1 0 1 1 0 0
2 0 0 1 0 1
3 0 0 0 1 0
4 0 0 0 0 1
5 0 0 0 0 0
Desde
Hasta
Principios de Computadoras IIGrafosRicardo Coppo
17Universidad Nacional del Sur
Matriz de adyacencia
1 2 3 4 5
1 ∞ 5 7 ∞ ∞
2 ∞ ∞ 3 ∞ 9
3 ∞ ∞ ∞ 2 ∞
4 ∞ ∞ ∞ ∞ 6
5 ∞ ∞ ∞ ∞ ∞
Desde
Hasta
1
3 4
25
5
7
3
2
9
6
Se utiliza un valor “centinela” en las celdas de los arcos no existentes. El “0” puede confundirse como costo nulo.
Principios de Computadoras IIGrafosRicardo Coppo
18Universidad Nacional del Sur
Matriz de adyacencia� Problemas con esta representación:
� Se almacena mucha información de arcos no existentes. (Tablas “ralas”)
� El uso de memoria es del orden O(V2). (Crece con el cuadrado de la cantidad de vértices)
Principios de Computadoras IIGrafosRicardo Coppo
19Universidad Nacional del Sur
Listas de adyacencia
1
3 4
25
1 2
2
3
4
5
3
3 5
4
5
Si el grafo es ponderado el nodoalmacena el costo también
Principios de Computadoras IIGrafosRicardo Coppo
20Universidad Nacional del Sur
Algoritmos principales� Operaciones de creación, inserción y
eliminación de vértices y aristas en el grafo.
� Ordenación topológica
� Caminos de costo mínimo
Principios de Computadoras IIGrafosRicardo Coppo
21Universidad Nacional del Sur
Ordenación topológica� Es una ordenación de los vértices de un
grafo dirigido acíclico tal que si hay un camino de vi a vj entonces vi precede a vj en la secuencia.
1
3 4
25
Orden topológico = { 1, 2, 3, 4, 5 }
Principios de Computadoras IIGrafosRicardo Coppo
22Universidad Nacional del Sur
Grado de entrada � Se define como grado de entrada de un
vértice en un grafo dirigido acíclico a la cantidad de aristas que finalizan en dicho vértice.
Grado de entrada = 3
Principios de Computadoras IIGrafosRicardo Coppo
23Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
Orden topológico = { }
Principios de Computadoras IIGrafosRicardo Coppo
24Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
Orden topológico = { 1 }
Principios de Computadoras IIGrafosRicardo Coppo
25Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
Orden topológico = { 1 }
Principios de Computadoras IIGrafosRicardo Coppo
26Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
Orden topológico = { 1, 5 }
Principios de Computadoras IIGrafosRicardo Coppo
27Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
0 2 1 1Orden topológico = { 1, 5 }
Principios de Computadoras IIGrafosRicardo Coppo
28Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
0 2 1 1Orden topológico = { 1, 5, 2 }
Principios de Computadoras IIGrafosRicardo Coppo
29Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
0 2 1 1
1 1 0
Orden topológico = { 1, 5, 2 }
Principios de Computadoras IIGrafosRicardo Coppo
30Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
0 2 1 1
1 1 0
Orden topológico = { 1, 5, 2, 6 }
Principios de Computadoras IIGrafosRicardo Coppo
31Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
0 2 1 1
1 1 0
0 1
Orden topológico = { 1, 5, 2, 6 }
Principios de Computadoras IIGrafosRicardo Coppo
32Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
0 2 1 1
1 1 0
0 1
Orden topológico = { 1, 5, 2, 6, 3 }
Principios de Computadoras IIGrafosRicardo Coppo
33Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
0 2 1 1
1 1 0
0 1
0
Orden topológico = { 1, 5, 2, 6, 3 }
Principios de Computadoras IIGrafosRicardo Coppo
34Universidad Nacional del Sur
Ordenación topológica
1 2
5
4
6
31 2 53 4 6
0 2 12 1 1
1 02 1 1
0 2 1 1
1 1 0
0 1
0
Orden topológico = { 1, 5, 2, 6, 3, 4 }
Principios de Computadoras IIGrafosRicardo Coppo
35Universidad Nacional del Sur
Ordenación topológica� Algoritmo
1. Calcular el grado de entrada para todos los vértices del grafo
2. Identificar los vértices con grado 0 (puede haber mas de uno) y asignarles un número de orden
3. Restar 1 al grado de entrada a todos los vértices adyacentes a los identificados en el punto anterior.
4. Si quedan vértices sin ordenar, repetir los pasos 2 y 3.
Principios de Computadoras IIGrafosRicardo Coppo
36Universidad Nacional del Sur
Ordenación topológica� Ideas para la implementación
� Usar listas enlazadas para almacenar los vértices “ordenados” y “sinProcesar”. A medida que se procesa el grafico se pasan los nodos de una lista a otra.
� Puede ser necesaria una clase auxiliar que almacena la información del vértice y del grado de entrada actual para facilitar el uso de las listas.
� No debe destruirse el grafo original.
Principios de Computadoras II
Grafos
Departamento de Ingeniería Electrónica y ComputadorasUniversidad Nacional del Sur
Ricardo [email protected]
Top Related