GIIT_AMA_18_Grafos_Ejercicios

229 days ago by etlopez18

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

Alumnos que integran el grupo

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

Ejercicios

PARTE A) (DE LOS TUTORIALES)

TUTORIAL 1

1. Genera un grafo cuyos vértices sean los números naturales del 1 al 20 y dos vértices sean adyacentes si los números son congruentes módulo 4.

2. Crea una función que reciba una lista de números y genere el grafo cuyos vértices son los números de la lista y dos vértices serán adyacentes si la diferencia de los números es 3 o superior.

3. Vamos a crear una función que calcule la componente conexa de un vértice. La función recibira un grafo y un vértice v y seguirá el siguiente algoritmo:

    a) Inicializará una lista L con el vértice v

    b) Calculará la lista de vértices adyacentes a alguno de L pero que no esté en L

    c) Mientras la lista de vértices adyacentes del apartado anterior no sea vacía, repetirá a) y b)

 
       

TUTORIAL 2

1. Representa en una misma gráfica el grafo de Petersen y su complementario (el grafo compuesto por los mismos vértices y las aristas complementarias). Para ello representa el grafo completo, creando una copia del grafo de Petersen (puedes usar copy o crear otro nuevo con graphs) y añade las aristas que no estén (por ejemplo, recorriendo todas las parejas u,v de vértices del grafo y añadiendo las aristas que no estén). Puedes usar una nueva etiqueta para las aristas que añadas y así simplificas dibujarlas. Dibuja en un color las aristas que no estén en el grafo de Petersen y en otro las que estén.

 
       

PARTE B) EJEMPLOS

Elegid dos apartados, el apartado correspondiente a la última cifra de la suma de vuestros DNIs, y  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.

 
       

PARTE 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 cinco 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.


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

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

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

4. 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. Rellenar en la parte superior el nombre de los integrantes del grupo.
  2. Compartir esta hoja de Sage con el profesor (etlopez18).
  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.