GIIT_AMA_1718_T2_Ejercicios

503 days ago by GIIT_AMA_1718

Práctica de Ampliación de Matemáticas (Tema 2: Teoría de Grafos)

Alumnos que integran el grupo

  1. ...
  2. ...
  3. ...

Ejercicios

 
       

A. Trabajando con grafos.

En este ejercicio se pueden utilizar todas las funciones para grafos de Sage.

1. Carga el grafo "laberinton.png" donde n-1 es el resto de dividir la suma de los DNI's de los miembros del grupo entre7.

2. Encuentra un camino entre el vértice (1,1) y el (59,79). dibuja el grafo con el camino en otro color.

3. Encuentra un camino (y dibújalo cambiando el color de los vértices del camino) entre el vértice (1,1) y

  • el vértice (11,11) si has cargado el laberinto 1.
  • el vértice (19,11) si has cargado el laberinto 2.
  • el vértice (31,31) si has cargado el laberinto 3.
  • el vértice (11,25) si has cargado el laberinto 4.
  • el vértice (41,41) si has cargado el laberinto 5.
  • el vértice (35,41) si has cargado el laberinto 6.
  • el vértice (7,47) si has cargado el laberinto 7.

4. Encuentra un ciclo en el grafo. Dibuja el grafo, cambiando el color de los vértices del ciclo.

5. Considera el grafo formado por "las paredes", es decir, aquel cuyos vértices son los píxeles negros y los vértices adyacentes son los píxeles negros situados en las cuatro posiciones adyacentes (izquierda, derecha, arriba, abajo). Obtén la componente conexa del vértice que prefieras.

 
       

B. Ejemplos.

Elegid dos apartados, el apartado correspondiente a la última cifra de la suma de vuestros DNIs el apartado correspondiente a la última cifra de la suma de vuestros DNIs más cinco. Obtener para cada apartado un grafo que cumpla las propiedades pedidas. Debéis incluir el grafo y explicar por qué cumple las propiedades. En caso de que penséis que no existe dicho grafo, justificar porqué.

0. Hamiltoniano con un conjunto independiente formado por 4 vértices.

1. Conexo, 4-regular pero no hamiltoniano.

2. Euleriano con complemento 3-regular.

3. 4 regular, euleriano y no hamiltoniano.

4. No euleriano con secuencia de grados 4,2,2,2,2,2,2,2

5. 4 regular, pero ni plano ni hamiltoniano.

6. 4-regular, no completo y con radio y diámetro igual a 4.

7. Plano, 5-regular.

8. Hamiltoniano, bipartito, 3-regular

9 Plano, bipartito, Euleriano y con al menos un vértice de grado 6.

 
       

C. Algoritmos.

En los siguientes ejercicios se tratará de codificar funciones sencillas de teoría de grafos, para repasar los conceptos y algoritmos. Sage tiene predefinidas montones de funciones que hacen todas esas operaciones, pero el objetivo es que vosotros aprendáis cómo se trabaja con grafos, por lo que en la resolución deberéis usar únicamente lo que se ha explicado en las prácticas. Las funciones tienen que estar convenientemente explicadas, con un comentario al comienzo de la función como líneas de comentario en cada operación que se considere compleja (en particular en los bucles y llamadas recursivas).

Crea varios grafos de prueba, codifica la función descritas en el apartado correspondiente al resto de dividir entre tres la suma de los DNI's (hay dos listas según el grado al que pertenezcan los miembros del grupo) y pruébala. Se recomienda crear funciones intermedias para los pasos del algoritmo. (Podéis consultar al profesor para resolver cuestiones de programación.)

Todos los miembros del grupo de informática o grupo con algún miembro de informática:

0. Crea una función que reciba un grafo y devuelva un circuito euleriano (en caso de que no exista, devolverá un grafo vacío).

1. Crea una función que reciba un grafo y devuelva su polinomio cromático.

2. Crea una función que reciba un grafo etiquetado y dos vértices y devuelva el flujo máximo entre los dos vértices. (Para calcular un camino entre dos vértices podéis usar algún método de Sage.)

Todos los miembros del grupo de telemática o doble grado:

0. Crea una función que reciba un grafo etiquetado (con etiquetas positivas) y dos vértices, a,b, y devuelva

a: la distancia mínima entre a y b.

b: el camino óptimo entre a y b.

1. Crea una función que reciba un grafo y devuelva el árbol recubridor minimal por el algoritmo de Kruskal. Se valorará además que el algoritmo devuelva los pasos intermedios mediante un grafo con etiquetas diferentes para las aristas visitadas y descartadas.

2. Crea una función que reciba un grafo y devuelva el árbol recubridor minimal por el algoritmo de Prim. Se valorará además que el algoritmo devuelva los pasos intermedios mediante un grafo con etiquetas diferentes para las aristas visitadas y descartadas.

 
       

Planificación y trabajo en equipo

Trabajo en equipo

Cada miembro del equipo, deberá subir una memoria que contenga, al menos, los siguientes items:

  • Metodología seguida. Indicar cómo se ha organizado el trabajo, en qué tareas se ha dividido y a quien han sido asignadas. 
  • Calendario de trabajo. Indicar las reuniones que se vayan a programar y cómo se realizará la coordinación entre los miembros del equipo.
  • Incidencias. 

Planificación

Cada alumno debe subir una memoria con los siguientes puntos:

  • Planificación inicial. Una vez que se haya producido el reparto de tareas del equipo, deberá elaborar una planificación donde figurarán las distintas tareas que debe realizar, un tiempo estimado para cada una y el periodo de tiempo en el que lo realizará.  
  • Tiempo total empleado y tiempo empleado en cada tarea. 

Normas de entrega

  1. Rellenar en la parte superior el nombre de los integrantes del grupo.
  2. Compartir esta hoja de Sage con el profesor (GIIT_AMA_1718).
  3. En el desplegable "File" de la parte superior de la página, elegir "Print"
  4. Imprimir la página resultante como pdf. 
  5. Subirla al campus virtual antes de la fecha límite, junto con la memoria de planificación y trabajo en equipo. Cada día a partir de la fecha límite, la nota sobre la que se puntúa el ejercicio bajará en un punto.

Criterios de evaluación

  • 40% de la calificación que los resultados y métodos aplicados sean correctos.
  • 15% de la calificación que los resultados estén correctamente explicados.
  • 15% de la calificación que los métodos empleados sean los más adecuados al problema.
  • 15% de la calificación que el trabajo haya sido convenientemente planificado (http://matematicas.unex.es/~trinidad/misc/planificacion.rubrica.pdf).
  • 15% de la calificación que se haya organizado el trabajo en equipo (http://matematicas.unex.es/~trinidad/misc/trabajo.equipo.rubrica.pdf).