GIIT_AMA_1314_Arboles_Mapas_Coloraciones

1399 days ago by trinidad

Árboles, mapas y coloraciones

Árbol de una función recursiva

Si tenemos una función recursiva, podemos considerar el grafo cuyos vértices son cada uno de los conjuntos de parámetros para los que se ha llamado la función y tenemos una arista que va desde un vértice v a otro w si la función con parámetro v llama a w.

El siguiente "decorador" crea el grafo de llamadas de  una función recursiva.

def grafo_llamadas(f): class G(object): def __init__(self, f): self.f=f self.stack = [] self.g = DiGraph() def __call__(self, *args, **kwds): if self.stack: sargs = ','.join(str(a) for a in args) last = ','.join(str(a) for a in self.stack[-1]) if self.g.has_edge(last, sargs): l = self.g.edge_label(last, sargs) self.g.set_edge_label(last, sargs, l + 1) else: self.g.add_edge(last, sargs, 1) else: self.g = DiGraph() self.stack.append(args) v = self.f(*args) self.stack.pop() return v def grafo(self): return self.g return G(f) 
       

Para usar el decorador, debemos escribir @grafo_llamadas en la celda en la que definamos la función.

@grafo_llamadas def fibo(n): if n<=2: return 1 else: return fibo(n-1) + fibo(n-2) 
       

El decorador nos generará el grafo de llamadas cada vez que ejecutemos la función. Las etiquetas de las aristas indican cuantas veces se ha pasado por esa arista en la llamada.

fibo(6) g = fibo.grafo() g.show(edge_labels=True) 
       
fibo(7) g = fibo.grafo() g.show(edge_labels=True) 
       

El decorador @cached_function hace que una función recursiva vaya guardando los valores que calcula.

@grafo_llamadas @cached_function def fibo_cached(n): if n<=2: return 1 else: return fibo_cached(n-1) + fibo_cached(n-2) 
       
fibo_cached(6) g = fibo_cached.grafo() g.show(edge_labels=True) 
       

Veamos un segundo ejemplo con las particiones de un número (una partición de un número natural n es una sucesión de números k1, ..., kr tal que n=k1+k2+...+kr).

@grafo_llamadas def particiones(n, k): if k == n: return [[1]*n] if k == 1: return [[n]] if not(0 < k < n): return [] ls1 = [p+[1] for p in particiones(n-1, k-1)] ls2 = [[parte+1 for parte in p] for p in particiones(n-k, k)] return ls1 + ls2 
       
particiones(8,3) g = particiones.grafo() g.show(edge_labels=True, figsize=(8,8), vertex_size=500) 
       
particiones(10,4) g = particiones.grafo() g.show(edge_labels=True, figsize=(8,8), vertex_size=500) 
       

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 elije en el $A$ los apartados que correspondan a tu última cifra del DNI (a la última cifra de la suma de DNI si sois dos), 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.

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

2, 7. Grafo bipartito completo (n,m). Está formado por dos conjuntos de vértices, el primero con n elementos y el segundo con m, de modo que los vértices del primer conjunto estan unidos con todos los del segundo conjunto.

3, 6, 0.  Grafo tres en raya. Cada posición del tablero se denota con un número (1 a 9). Cada jugada se representa símplemente por la posición en la que se ha colocado la ficha. Los vértices del grafo serán la secuencia de jugadas hasta ese momento y las aristas la jugada anterior. Así, si el primer jugador pone ficha en 1, el segundo en 4, el primero en 2 y el segundo en 3, tendremos 1,4,2,3 y una arista (al menos) de 1,4,2 a 1,4,2,3.

4, 5, 9. Grafo de 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.

 
       

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

Informática:

3,2,5,0,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).

4,1,6,9,8. Crea una función que reciba un grafo y devuelva su polinomio cromático.

Telemática y doble grado:

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

6,9,2,4. 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.

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