Matee

Representación de grafos
Las representaciones de grafos más habituales están basadas en matrices de adyacencia y listas de adyacencia. En este ejercicio se pretende representar distintos grafosutilizando tanto matrices como listas de adyacencia.

Apartado a)
El plan de estudios de determinada titulación se compone de 6 asignaturas, que por simplicidad, denominaremos y . A la hora dematricularse de las distintas asignaturas se ha de tener en cuenta una serie de dependencias entre ellas (prerrequisitos). De esta forma, un alumno no se puede matricular en una asignatura hasta haberaprobado aquellas otras que sean prerrequisito de dicha asignatura. Representaremos a continuación los prerrequisitos del plan de estudios como un grafo dirigido de dependencias. Por ejemplo, un arco delnodo al nodo indica que no es posible matricularse de sin haber aprobado previamente . A continuación se muestran las operaciones del TAD grafo necesarias para construir el grafo de dependencias.Teniendo en cuenta que una operación de la forma añade al grafo un arco con origen en y destino en , se pide: Representar gráficamente y mediante matrices de adyacencia cada uno de losgrafos , y .

Solución propuesta:

A continuación se muestra la representación gráfica de los grafos , y .


La representación basada en matrices de adyacencia utiliza dos componentes. Elprimero es un conjunto que contiene los nodos del grafo. El segundo es una matriz booleana que representa los arcos. Existe un arco entre un nodo y otro sii la posición de fila y columna tiene elvalor (representado por una ). Las casillas vacías tienen valor .



Apartado b)
Una compañía telefónica desea realizar un estudio sobre las llamadas que realizan sus abonados. Para ello, sedesea construir un grafo cuyos nodos son los abonados (identificados por su número de teléfono). La existencia de un arco con origen en el nodo y destino en el nodo indica que el abonado ha llamado...