teoria de grafosteoria de grafos ¿ que es un grafo? un grafo es un conjunto de nodos o vértices...
TRANSCRIPT
TEORIA DE GRAFOS
¿ Que es un Grafo?
Un GRAFO es un conjunto de nodos o vértices (V) y
un conjunto de aristas (E), donde cada arista
relaciona a un par de nodos pertenecientes a V.
La estructura algebraica para los grafos es G=(V,E).
Existen dos tipos de Grafos:
GRAFO DIRIGIDO
GRAFO NO DIRIGIDO
GRAFO DIRIGIDO
Un GRAFO DIRIGIDO G consiste de un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo.
Los vértices de un grafo dirigido pueden usarse
para representar objetos y los enlaces relaciones entre los objetos, ejemplo de ello que los vértices pueden representar ciudades y los enlaces vuelos aéreos entre ciudades.
Un enlace es un par ordenado de vértices (v, w), donde v es la cola y w corresponde a la cabeza del enlace.
a b
c d
V={a, b, c, d}
E={(a,c), (a,b), (b,c),
(b,d), (c,d)} v w
GRAFO NO DIRIGIDO
• Sea G un Grafo no Dirigido,
donde G=(V,E) y V
corresponde al conjunto de
vértices y E al conjunto de
aristas del grafo.
• Un Grafo no Dirigido se
diferencia de un Grafo Dirigido
debido a que cada arista en E
es un par no ordenado de
vértices. Si (v,w) es una arista
no dirigida (v,w) = (w,v).
a b
c d
V={a, b, c, d}
E={(a,c),(c,a),(a,b),(b,a)
(b,c),(c,b),(b,d),(d,b),
(c,d),(d,c)}
COSTOS
Grafo Dirigido
Etiquetado Grafo No Dirigido
Etiquetado
Los enlaces tanto para los grafos Dirigidos como No
Dirigidos tienen un costo (valor), por lo tanto son grafos
etiquetados.
a b
c d
a b
c d
20
30 25
15
40 40
a b
c d
a b
c d
20
30 25
15
REPRESENTACION LOS GRAFOS
Un grafo Dirigido o No-Dirigido se puede representar
mediante:
Matriz de Adyacencia
Lista de Adyacencia
Arreglos para la Lista de Adyacencia.
Sea el siguiente Grafo Dirigido:
Donde: V={1,2,3,4} E={(1,2),(2,3), (,3,1), ((4,2),(3,4)}
2
1
3
4
MATRIZ ADYACENTE
casootroen
Ejisijia
0
),( 1],[
Sea: E={( 1 , 2 ), ( 2 , 3), (3 , 1 ), ( 4 ,2),( 3 , 4 )}
0010
1001
0100
0010
a
La Matriz Adyacente A de un Grafo G=(V,E) tiene V*V elementos y se define como:
Fila Columna
2
1
3
4
VENTAJAS Y DESVENTAJAS DE LA MATRIZ DE ADYACENCIA
• VENTAJAS: Se puede determinar en un tiempo
fijo y constante si un enlace(arco) pertenece o no al grafo.
Es fácil determinar si existe o no un arco o enlace, solo se debe posicionar en la matriz.
Es fácil determinar si existe un ciclo en el grafo, basta multiplicar la matriz por ella misma n veces hasta obtener la matriz nula(no hay ciclos) o bien una sucesión periódica de matrices(hay ciclo)
• DESVENTAJAS:
Se requiere un almacenamiento |v|*|v|. Es decir O(n2).
Solo al leer o examinar la matriz puede llevar un tiempo de O(n2).
LISTA ADYACENTE
La lista de adyacencia para un vértice v es una lista enlazada de todos los vértices w adyacentes a v. Un grafo puede ser representado por |v| listas de adyacencias, una para cada vértice.
=
1
2
2 3
=
3 4
3
2 1
3 4
4
= 2
=
Lista de
Adyancencia Grafos
Vértices
VENTAJAS Y DESVENTAJAS
DE LAS LISTAS DE ADYACENCIA
• VENTAJAS: La lista de adyacencia requiere
un espacio proporcional a la suma del número de vértices más el número de enlaces(arcos). Hace buen uso de la memoria.
Se utiliza bastante cuando el número de enlaces es mucho menor que O(n2)
• DESVENTAJAS: La representación con lista de
adyacencia es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que pueden haber O(n) vértices en la lista de adyacencia. Para el vértice i.
UTILIZACION DE ARREGLOS
PARA LA LISTA DE ADYACENCIA
21
3 4
Grafos
1
2
4
3
Vertices
2
3
0
4
0
2
0
3
0
Arreglo de
Lista
Adyacente
Se utilizan los arreglos para implementar la Lista de Adyacencia:
EJERCICIOS
Para los siguientes Grafos Dirigidos y No Dirigidos, calcular su:
• Matriz de Adyacencia
• Lista de Adyacencia
Construya la Matriz de adyacencia del siguiente
grafo no dirigido:
1
3
5
8
Ejercicio 1
Construya la Matriz de adyacencia del siguiente
Grafo Dirigido:
1
4
2
3
Ejercicio 2
a b
c d
a b
c d
8
30 15
15
40 40
a b
c d
a b
c d
120
10 5
15
Ejercicio 3 Ejercicio 4
A partir de las siguientes Matrices,
construir sus respectivos Grafos si es
que es posible.