GIIT_AMA_1415_Ejercicios_Grafos_2

1097 days ago by trinidad1415

Práctica de Ampliación de Matemáticas (Tema 2: Caminos, mapas, coloraciones)

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,3. Completo, etiquetado, y tal que el camino óptimo entre dos vértices recorra todos los vértices.

1,2. Completo, etiquetado, y con un único árbol recubridor minimal que además tenga un único vértice de grado 4 (el árbol).

2,1. Plano, euleriano y 4 regular.

3,0. Euleriano, pero no plano ni hamiltoniano.

4,9. Plano, 4 regular, pero  no euleriano ni hamiltoniano.

5,8. Hamiltoniano, euleriano y no plano.

6,7. Etiquetado y tal que el algoritmo de Dijkstra modifique cada valor de $L$ (excepto para los dos primeros vértices) exactamente dos veces.

7,6. Euleriano, plano y con número cromático tres.

8,5. Hamiltoniano, euleriano, 4 regular y que se pueda colorear con dos colores (bipartito).

9,4. Etiquetado y tal que los algoritmos de Prim y Kruskal generen la misma secuencia de aristas.


 
       

B. Crea una función que genere los grafos indicados en el apartado correspondiente. Además, discutir si los grafos generados pueden ser, conexos, eulerianos, hamiltonianos, árboles o planos.

4,5,7. Grafo de Hamming. El grafo de hamming de $n$ es una función cuyos vértices son los número binarios hasta $2^n-1$ y las aristas unen dos vértices si se diferencian en un bit. Además, se creará una función que diga en cuantos bits se diferencias dos números binarios usando el grafo anterior (para esto se puede usar cualquier método de Sage).

1,8,0. Grafo de conexión una imagen binaria. Recibirá una matriz de unos y ceros. Los vértices serán los unos y los vértices adyacentes son los que se situan en la posición inmediatemente superior, inferior, izquierda o derecha. Además, devolver el número de componentes conexas del grafo (para esto se puede usar cualquier método de Sage).

2,3,6,9. Grafo de restricciones. Supongamos que tenemos una lista de recursos compartidos por varios procesos. Por cada recurso creamos una lista con los identificadores de los procesos que lo utilizan. Crear un grafo cuyos vértices sean los procesos y dos procesos serán adyacentes si comparten un mismo recurso. Devolver además el máximo número de procesos que se pueden ejecutar simultáneamente sin entrar en conflicto con los recursos (para esto se puede usar cualquier método de Sage).




 
       

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

Informática o grupo con algún miembro de informática:

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

2,5,8. Crea una función que reciba un grafo y devuelva su polinomio cromático.

0,3,6,9. Crea una función que reciba un grafo etiquetado y dos vértices y devuelva el flujo máximo entre los dos vértices.

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

1,4,7 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.

2,5,8. 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.

0,3,6,9. 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.

 
       

Normas de entrega

  1. Renombrar la hoja como GIIT_AMA_1415_Tema_2_P2_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_Tema_2_P2_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.