Sesion_3_representacion_grafos ver 3

Vista previa del material en texto

Representación de 
Grafos
Teoría de Grafos
Nivel 9
Temas a tratar
Teoría de Grafos
Nivel 9
• Matriz de adyacencia
• Matriz de incidencia
• Lista de adyacencia
Representación de Grafos
Representación 
de Grafos
NO Gráfica
Forma Matricial
Adyacencia
Incidencia
Forma de Lista
Gráfica
Cuando se quieren programar algoritmos que 
utilizan grafos, se necesita una representación no 
gráfica que pueda utilizarse en la computador.
Matriz de Adyacencia (MA)
Es una matriz de tamaño n × n donde las filas y 
las columnas hacen referencia a los vértices para 
almacenar en cada celda la longitud entre cada 
par de vértices del grafo. En la celda MA[i, j] se 
almacena la longitud entre el vértice i y el vértice 
j, para el caso de los grafos ponderados.
Matriz de Adyacencia (MA)
Para el caso de los grafos NO ponderados, la 
celda MA[i, j] almacena 1, si existe una arista 
entre el vértice i y el vértice j. De lo contrario su 
valor es infinito, lo cual significa que no existe 
arista entre esos vértices, y MA[i, i] = ∞. 
Matriz de Incidencia (MI)
La matriz de incidencia es una matriz binaria de 
n x m (sus elementos (valores de MI[i, j] ) sólo 
pueden ser unos o ceros), que se utiliza como 
una forma de representar relaciones binarias.
Matriz de Incidencia (MI)
Construcción de la 
matriz de 
incidencia a partir 
de un grafo
1. Las columnas de la matriz 
representan las aristas del grafo 
2. Las filas representan a los 
distintos nodos.
3. Por cada nodo unido por una 
arista, se pone un uno (1) en la 
celda correspondiente, y se 
rellena el resto de las celdas con 
ceros (0).
Lista de Adyacencia (LA)
Se utiliza un vector de tamaño n (un elemento por 
cada vértice) donde LA[i] almacena la referencia a 
una lista de los vértices adyacentes a i. La lista 
almacenará también la longitud de la arista que 
va desde i al vértice adyacente. 
Se almacenan pares de datos 
(Vértice adyacente, peso arista)
Ejemplo
Sea G un grafo no 
dirigido, elaborar 
la matriz de 
adyacencia, lista 
de adyacencia y 
matriz de 
incidencia. 
G
Ejemplo – Matriz de Adyacencia (MA)
G
1 2 3 4 5 6 7
1 0 8 1 ∞ ∞ ∞ ∞
2 8 0 5 2 ∞ ∞ ∞
3 1 5 0 7 5 ∞ ∞
4
5
6
7
Ejemplo – Lista de Adyacencia (LA)
G
1
2
3
4
5
6
7
2 8 3 1
1 8 3 5 4 2
1 1 2 5 4 7 5 5
Vértice 
Adyacente
Peso Arista
Ejemplo – Matriz de Incidencia (MI)
G
1 2 3 5 5 7 8 9
1 1 0 0 0 0 0 1 0
2 0 1 0 1 0 0 1 0
3 1 0 0 1 1 1 0 0
4 0 1 0 0 0 1 0 0
5 0 0 1 0 1 0 0 1
6 0 0 0 0 0 0 0 1
7 0 0 1 0 0 0 0 0
Aristas
v
ér
ti
ce
s
Ejemplo – Matriz de Incidencia (MI)
Ejemplo
Construya la matriz de 
adyacencia y la lista de 
adyacencia.
a b
d c
a
b
d
c
G
G’
e
Ejemplo
a b
d c
G
e
a b c d e
a 0 1 1 1 ∞
b 1 0 1 1 ∞
c 1 1 0 1 ∞
d 1 1 1 0 ∞
e ∞ ∞ ∞ ∞ 0
Matriz de adyacencia
Ejemplo
a b
d c
G
e
a
b
c
d
e
b
Null
c Null
a
Null
a
Null
d Null
c Null d Null
b Null d Null
a
Null
b Null c Null
Lista de adyacencia
Ejemplo
a b c d
a 0 1 ∞ ∞
b ∞ 0 1 1
c ∞ 1 0 1
d 1 ∞ ∞ 0
Matriz de adyacencia
a
b
d
c
G’
Referencias
DE LA HOZ, Alexis, DE LA HOZ FRANCO, Emiro, Paola Ariza Colpas. 
Árboles y grafos. Editorial EDUCOSTA. 2009
Muchas gracias por su atención