Alumno : Víctor Hugo Orellana Jaque!Análisis de Algoritmos Sección 112!Profesora : Sra. Pilar Pardo Hidalgo!

26-junio-2014!

¿Qué 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. (Tal como en un poliedro, donde una arista relaciona a dos vértices)! Algebraicamente, los grafos se representan así : G=(V,E)! Dos tipos de grafos existen : Dirigidos y No Dirigidos!

Grafos Dirigidos!Ø Un grafo dirigido 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 objetos. La èindica en qué dirección se recorre el grafo.!

Ø Un enlace es un par ordenado de vértices (a,b) donde : !

b  a  

cola   cabeza  

Grafos No Dirigidos!u Sea G un grafo no dirigido, donde

G=(V,E) y V es el conjunto de vértices y E el conjunto de aristas del grafo.!

u A diferencia de un grafo dirigido, en este tipo de grafos cada arista en E es un par no ordenado de vértices. La siguiente situación sucede :!

(a,b)=(b,a)!

!

a   b  

Costos!•  Los enlaces tanto para los grafos no

dirigidos como para los dirigidos tienen un costo, o valor, por lo tanto son grafos etiquetados. !

•  Los valores se etiquetan en la arista.!

Representación de los Grafos!

!•  Un grafo dirigido o no dirigido puede ser

representado mediante:!a)  Matriz de Adyacencia!b)  Lista de Adyacencia!c)  Arreglos para la Lista de Adyacencia!

Matriz Adyacente!

•  La matriz adyacente A de un grafo G=(V,E) tiene V*V elementos y se define como:!

a(i,j)  =        1  si    (i,j)  ∈  E                                                              0  en  otro  caso     Considerando “i” a las filas y “j” a las columnas.!

Ventajas y Desventajas : Matriz de Adyacencia!

Ventajas   Desventajas  

Se  puede  determinar  en  un  2empo  fijo  y  constante  si  un  enlace  pertenece  o  no  al  grafo.  

Se  requiere  almacenamiento  |v*v|  .  O  sea  O(n2).  

Es  fácil  determinar  si  existe  o  no  un  arco  o  enlace,  sólo  se  debe  posicionar  en  la  matriz.  

Sólo  al  leer  o  examinar  la  matriz  puede  llevar  un  2empo  de  sea  O(n2)  ,  siendo  por  ende,  demoroso.  

Es  fácil  determinar  si  existe  un  ciclo  en  el  grafo,  para  eso  se  debe  mul2plicar  la  matriz  por  ella  misma  “n”  veces  hasta  obtener  una  matriz  nula  (Matriz  solo  con  valores  0)  o  bien,  una  sucesión  periódica  de  matrices  (hay  ciclo)  

Lista Adyacente!

v La lista adyacente 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 adyacencia, una para cada vértice.!

v La lista de adyacencia depende de a qué vértices pueda recorrer al vértice adyacente !

Ventajas y Desventajas : Listas de Adyacencia!

Ventajas   Desventajas  

La  lista  de  adyacencia  requiere  un  espacio  proporcional  a  la  suma  del  número  de  vér2ces  más  el  número  de  enlaces.  U2iza  de  buena  manera  la  memoria  

La  representación  con  lista  de  adyacencia  puede  llevar  un  2empo  O(n)  determinar  si  existe  un  arco  del  vér2ce  i  al  vér2ce  j,  debido  a  que  pueden  haber  O(n)  vér2ces  en  la  lista  de  adyacencia  para  el  vér2ce  indicado.  

Se  usa  bastante  cuando  el  número  de  enlaces  es  mucho  menor  que  O(n2)  

Arreglos para la lista de Adyacencia!

v Se utilizan arreglos para implementar la lista de adyacencia en este caso!

F I N

Gracias por su atención!