75.

569 · Grafos y Complejidad · PEC1

2023-24-Sem. 2 · Grado en Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

Presentación

Esta PEC es una introducción a la teorı́a de grafos que cubre los contenidos estudiados en los
3 primeros módulos de la asignatura. Los ejercicios trabajan tanto los conceptos previos sobre
funciones y algoritmos, los fundamentos de la teorı́a de grafos y los problemas de recorridos y
conectividades sobre grafos.

Competencias

En esta PEC se trabajan las siguientes competencias del Grado de Ingenierı́a Informática:

Capacidad para utilizar los fundamentos matemáticos, estadı́sticos y fı́sicos para comprender
los sistemas TIC.

Capacidad para analizar un problema en el nivel de abstracción adecuada en cada situación

y aplicar las habilidades y conocimientos adquiridos para resolverlos.

Objetivos

Los objetivos concretos de esta PEC son:

Conocer los principales conceptos de combinatoria.

Conocer el concepto de complejidad temporal y espacial de un algoritmo.

Conocer el concepto de grafo y los diferentes tipos de grafos (grafos orientados, grafos pon-
derados, pseudografos, multigrafos, ...).
Conococer las principales propiedades de los grafos y saber analizarlas.
Conocer los problemas de conectividad más usuales sobre grafos, los algoritmos que los re-
suelven y saber aplicarlos en un grafo concreto.
Ser capaz de representar y analizar un problema en términos de la teorı́a de grafos.

1
 75.569 · Grafos y Complejidad · PEC1
2023-24-Sem. 2 · Grado en Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

Descripción de la PEC a realizar

1. (Valoración de un 25 % = (4+4+4+1) %+(5+7) %)

a) Dados dos conjuntos finitos A y B de n y m elementos respectivamente, dad en función

de n y m:
1) Cuántas funciones inyectivas de A a B existen.
2) Cuántas funciones exhaustivas de A a B existen.
3) Cuántas funciones biyectivas de A a B existen.
4) Si n = m = 9, ¿Cuántas funciones biyectivas existirán?

b) Se quiere calcular la suma de todos los números que se obtienen al permutar las cifras
1, . . . , n, para n ≤ 9.
A modo de ejemplo, para n = 2, los números obtenidos al permutar las cifras 1 y 2 son:
12, 21, y su suma es 33.
1) Escribid el pseudocódigo de un algoritmo que permita calcular dicha suma. Para ello,
asumid que se tienen todos los números en una lista. ¿Cuántos segundos tardarı́a
un ordenador en hacer la suma para el caso n = 9 si cada operación aritmética le
cuesta 1 µs (no cuentes las asignaciones)?
2) Encontrad una fórmula cerrada para dicha suma. ¿Cuántos µs ahorramos respecto
al apartado anterior para n = 9 usando esta expresión?

2. (Valoración de un 20 %=7 % + 6 %+2 %+5 % )

a) Dibujad el grafo G = E4 × T3 , donde E4 es el grafo estrella de tres puntas. Dad la

secuencia de grados del grafo ordenada. ¿Cuántas aristas tendrá el grafo complementario
de G?
b) Dado otro grafo, H, con 11 aristas y grados (no necesariamente ordenados) x, y, 1, 2, 3, 4, 5.
1) ¿Cuáles son los posibles valores de x e y, con x > y > 1 que hacen que los grados
dados sean secuencia gráfica?
2) Dibujad el grafo y escribid su matriz de adyacencias.
3) Escribid un algoritmo en pseudocódigo que permita dibujar un grafo a partir de su
secuencia gráfica ordenada de mayor a menor. Podéis usar la función Conectar(u,v)
que dibuja una arista entre dos vértices u y v, y la función Grado(u), que devuelve
el número de aristas conectadas a u.

2
 75.569 · Grafos y Complejidad · PEC1
2023-24-Sem. 2 · Grado en Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

3. (Valoración de un 25 % = 7 % + 4 % + 10 % + 4 %)
Considerad el grafo no dirigido dado por la siguiente matriz de pesos:

A B C D E F G H
A 0 2 8 - - - - -
B 0 5 6 - - - -
C 0 3 x - - -
D 0 2 9 - -
E 0 3 - -
F 0 - -
G 0 3
H 0

donde x es un número natural positivo y el sı́mbolo “-” significa que los dos vértices no están
conectados directamente.

a) Calculad, mediante el algoritmo adecuado, a qué vértices es posible viajar (no nece-
sariamente por viaje directo) desde el vértice C. En caso de poder escoger más de un
vértice en el mismo paso del algoritmo, escoged en orden lexicográfico. Mostrad todos
los pasos del algoritmo.
b) Encontrad el diámetro del grafo.
c) Encontrad, mediante el algoritmo adecuado, la ruta más corta entre A y F e indicad su
distancia. Mostrad todos los pasos del algoritmo.
d ) ¿El algoritmo de Dijsktra da siempre con el resultado correcto si se permiten pesos nega-
tivos entre vértices? En caso afirmativo, justificad vuestra respuesta. En caso negativo,
aportad un contraejemplo.

4. (Valoración de un 30 %) Cuestionario de evaluación Moodle

Dentro del aula de la asignatura, en el Campus Virtual, encontraréis la herramienta Moodle.
En este Moodle hay un cuestionario con diversas preguntas que debéis resolver como último
ejercicio de esta PEC.
Leed atentamente las siguientes instrucciones antes de abrir el cuestionario:

Los contenidos que se evalúan en este cuestionario corresponden al módulo “Fundamen-

tos de grafos” y “Recorridos y conectividad”. Es importante que hayáis asimilado estos
conocimientos antes de abrir el cuestionario.
El cuestionario estará abierto durante el plazo de la PEC y lo podéis resolver cuando
queráis. De todas formas, una vez lo abráis tendréis un tiempo limitado para resolverlo
(1 hora).

3
 75.569 · Grafos y Complejidad · PEC1
2023-24-Sem. 2 · Grado en Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

Importante: El cuestionario quedará cerrado a las 23:59 de la fecha lı́mite de entrega.

Si empezáis a hacerlo después de las 22:59 del último dı́a, ¡tendréis menos de una hora
para hacerlo!
Las respuestas a las preguntas se tienen que introducir directamente en el cuestionario
Moodle. No es necesario que las entreguéis junto con el resto de respuestas de la PEC.
Las preguntas del cuestionario son aleatorias: cada estudiante recibirá un enunciado
diferente.
En algunas preguntas tendréis que introducir la respuesta en un formato especı́fico (p. ej.
con los valores ordenados de una determinada forma y sin espacios). Es muy importante
seguir fielmente el formato indicado a la hora de introducir vuestra respuesta.
Disponéis de 2 intentos para resolver el cuestionario. El objetivo de tener dos intentos es
poder solventar posibles problemas que hayáis tenido en la realización del cuestionario,
ya sean problemas técnicos o bien que hayáis abierto el cuestionario por error. Por tanto,
debéis tener en cuenta que:
• La nota que obtendréis en el cuestionario será la de vuestro último intento.
• Después del 1er intento, no recibiréis la calificación obtenida ni recibiréis feedback
sobre vuestra propuesta de solución. Por lo tanto, no recomendamos usar el 2o
intento para intentar mejorar nota, ya que puede ser que obtengáis una nota inferior.
• Si usáis el 2o intento, el enunciado que encontraréis será diferente del 1er intento.
• Podéis realizar los dos intentos en dı́as diferentes, siempre que sea dentro del plazo
de la PEC. Dispondréis de 1 hora para cada intento.
• Cada vez que iniciéis el cuestionario contará como un intento, aunque no enviéis
la respuesta. Por ejemplo, si habéis hecho el 1er intento y volvéis a abrir el
cuestionario, invalidaréis vuestro 1er intento y os quedaréis con la nota
del 2o .

4
 75.569 · Grafos y Complejidad · PEC1
2023-24-Sem. 2 · Grado en Ingenierı́a Informática
Estudios de Informática, Multimedia y Telecomunicación

Recursos

Recursos Básicos
Módulo didáctico 1. Conceptos previos: funciones y algoritmos.
Módulo didáctico 2. Fundamentos de grafos.
Módulo didáctico 3. Recorridos y conectividad.
Colección de problemas.

Recursos Complementarios
PECs y exámenes de semestres anteriores.
Programario para el estudio de algoritmos sobre grafos.
Enlaces: Applets interactivos sobre algoritmos de grafos.

Criterios de valoración
La PEC se tiene que resolver de forma individual. En caso que hayáis consultado recursos
externos, es necesario referenciarlos.
Es necesario justificar la respuesta de cada apartado. Se valorará tanto el resultado final como
la justificación dada.
En los apartados donde sea necesario aplicar algún algoritmo, se valorará la elección del
algoritmo apropiado, los pasos intermedios, el resultado final y las conclusiones que se deriven.

Formato y fecha de entrega

Hay que entregar un único documento PDF con las respuestas de todos los ejercicios. El nombre
del fichero tiene que ser: PEC1 [Link].

Este documento se tiene que entregar antes de las 23:59 del dı́a 06/04/2024. No se aceptarán
entregas fuera de plazo.