EJERCICIOS GRAFOS Y ARBOLES MULTICAMINOS

TAREA GRAFOS Y ARBOLES MULTICAMINO
ESTRUCTURAS DE DATOS


TEMA 1
Dado un árbol B de orden n, implementar una función que lo modifique de tal forma que las claves en cada página inviertan suorden. No olvide que si cambian el orden de las claves, debe cambiar el orden de las ramas. Ejemplo:



TEMA 2
Los grafos G1 y G2 son isomorfos, si los adyacentes de cada vértice de G1 tienen unaestructura similar a los adyacentes de su correspondiente vértice en G2. Ej.


Realizar un función llamada SonIsomorfos que reciba como parámetro a G1 y G2 y retorne un valor lógico que indique silos grafos son isomorfos o no.


TEMA 3
Un quad-tree es un TDA que se usa en informatica grafica para representar figuras planas en blanco y negro. Es un arbol en el cual los nodos hoja puedenrepresentar un blanco o un negro y los nodos internos no representan ningun color, pero siempre tienen exactamente 4 hijos.
Asumiendo que al figura esta en un plano, el arbol se construye a partir de lafigura con los siguientes pasos:
1. Dividir plano en 4 cuadrantes
2. Revisar cada cuadrante en el sentido del reloj
Si el cuadrante esta lleno de blancos, corresponde a una hoja blanca en el arbolSi el cuadrante esta lleno de negros, corresponde a una hoja negra en el arbol
Si el cuadrante esta parcialmente blanco y negro, corresponde a un nodo interno
Aplicar el mismo algoritmo pero parauna plano que equivalga al cuadrante que se esta revisando
Ejemplo:

Definir la estructura para representar un quad-tree e
a) Implemente una funcion que determine la altura del quad-tree
b)Implemente una procedimiento que dado un quad-tree genere la figura correspondiente.
NOTA: El tipo Figura puede ser una matriz de T o F(blanco o negro) de dimensiones 2k x 2k, donde k es la altura delquad-tree

TEMA 4

En ocasiones, dado un grafo no valorado, es necesario conocer la ruta de longitud más corta desde un vértice S del grafo hacia el resto. Un algoritmo que puede resolver este...