GIIT_AMA_1415_Ejercicios_Grafos

1104 days ago by trinidad1415

Práctica de Ampliación de Matemáticas (Tema 2: Grafos eulerianos y hamiltonianos)

Alumnos que integran el grupo

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

Ejercicios

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).

De los siguientes ejercicios elegid en el $A$ los apartados que correspondan a  la última cifra de la suma de vuestros DNIs, en el $B$ a la penúltima y así sucesivamente.

 
       

A. Genera un grafo con las siguientes propiedades (en caso de no existir, razona porqué no es posible un grafo así):

0,9. 3-regular con un conjunto independiente formado por 4 vértices

1,8. 3-regular con un clique formado por 5 vértices

2,7. 4-regular y euleriano

3,6. Euleriano y hamiltoniano

4,5. Euleriano pero no hamiltoniano

5,4. Conexo, 4-regular pero no hamiltoniano

6,3. No Euleriano pero sí hamiltoniano

7,2. No conexo, 2-regular y con el complemento 3-regular

8,1. Conexo, hamiltoniano pero no euleriano

9,0. No euleriano y con secuencia de grados 4 2 2 2 2 2 2.

 
       

B. Crea una función que reciba un grafo y devuelva:

0,5. La secuencia de grados

1,6. Si contiene o no un conjunto independiente de 3 vértices

2,7. Si contiene o no un clique de 3 vértices

3,8. Si el grafo es regular

4,9. Si el grafo es completo

 
       

C. Crea varios grafos de prueba, codifica la función descrita en el apartado y pruébala.

0,4,8. Crea una función que reciba dos caminos simples (listas de vértices), con el primero y el último en común y devuelva un ciclo.

1,5,9. Crea una función que reciba una secuencia (lista decreciente de números positivos) y devuelva un grafo con dicha secuencia de grados (en caso de que no exista, devolverá un grafo vacío).

2,6. Crea una función que reciba un grafo y un vértice y devuelva la componente conexa de dicho vértice, utilizando la suma de las potencias de la matriz de adyacencia.

3,7. Crea una función que reciba un grafo y una lista de vértices y calcule en número de componentes conexas del grafo resultante de eliminar dichos vértices. Para calcular el número de componentes conexas utilizará el método connected_components_number.

 
       

Normas de entrega

  1. Renombrar la hoja como GIIT_AMA_1415_P3_Apellido1_Apellido2_Apellido3, correspondiendo Apellido1, Apellido2 y Apellido3 al primer apellido de los alumnos integrantes del grupo, en orden alfabético.
  2. Compartir esta hoja de Sage con el profesor.
  3. En el desplegable "File" de la parte superior de la página, elegir "Print"
  4. Imprimir la página resultante como pdf. Nombrarla como GIIT_AMA_1415_P3_Apellidos1_Apellidos2_Apellidos3.pdf, correspondiendo Apellido1, Apellido2 y Apellido3 al primer apellido de los alumnos integrantes del grupo, en orden alfabético.
  5. Subirla al campus virtual antes de la fecha límite. 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

  • 50% de la calificación que los resultados y métodos aplicados sean correctos.
  • 20% de la calificación que los resultados estén correctamente explicados.
  • 20% de la calificación que los métodos empleados sean los más adecuados al problema.
  • 10% de la calificación que los miembros del grupo hayan trabajado homogéneamente y que hayan aprovechado las horas de prácticas.