Ejercicios arboles - grafos

1) Dado el siguiente árbol binario:

a) Represente el árbol mediante listas enlazadas

b) Calcular los recorridos preorden, inorden y postorden

2) Dado el siguiente array:

a) Represente el árbol binario, siendo A el nodo raíz

3) Sean los recorridos de un determinado árbol binario:

preorden ABCDEFG y en inorden CDBEAGF

a) Dibujar el árbol binario

b) Determinar el recorrido en postorden

4) Dada la lista de números: 4 19 -7 49 100 0 22 12

a) Construir el árbol binario de búsqueda, siendo 4 el nodo raíz

b) Insertar el elemento 10 en el árbol

c) Eliminar el elemento 49 del árbol

d) Insertar el elemento 1 en el árbol

proponer el algoritmo y el código en C++ que realice dichas operaciones.

5.-Utilizar el algoritmo de Dijkstra para encontrar los caminos más cortos que van desde el nodo a hasta los restantes nodos, en el siguiente grafo dirigido. Mostrar los valores S, D y P para todos los pasos de ejecución del algoritmo.

6.-En general, dados dos nodos v, w en un grafo ponderado, puede existir más de un camino mínimo entre ambos (aunque necesariamente todos tendrán el mismo coste). Explicar cómo se debe modificar el algoritmo de Dijkstra para contar el número de caminos mínimos distintos existentes entre un nodo v y el resto de nodos.

7.- Determinar cuál es el orden de complejidad del algoritmo para encontrar las componentes fuertemente conexas en un grafo dirigido. Suponer que el grafo tiene n nodos y a aristas, siendo a>n.

8.- Aplicar el algoritmo para obtener las componentes fuertemente conexas para el grafo del ejercicio 5(a). A partir del resultado obtenido, mostrar el grafo reducido correspondiente.

9.- Mostrar el resultado de la aplicación del algoritmo de Floyd sobre el siguiente grafo dirigido. Con el resultado del algoritmo, calcular cuál es el nodo más central del grafo.

10.- Para desarrollar la especificación formal del TAD grafo dirigido y etiquetado disponemos de los siguientes conjuntos:

G Conjunto de grafos dirigidos y etiquetados

M Conjunto de nodos de los grafos

E Conjunto de valores de las etiquetas en las aristas

N Conjunto de naturales

B Conjunto de booleanos

U Conjunto de mensajes de error

Escribir la parte de sintaxis correspondiente a las operaciones que son los constructores del tipo. Poner también la sintaxis de alguna operación de modificación y otra de consulta sobre el grafo.

11.- Supongamos que se tienen cuatro aulas y las siguientes materias con susrespectivos horarios para un mismo día:

Álgebra I 8 a 12 hs.Análisis I 10 a 14 hs.Análisis II 14 a 18 hs.Lineal 11 a 15 hs.Analisis III 12 a 16 hs.Complejo 9 a 13 hs.Operativa 14 a 18 hs.Estadística 14 a 18 hs.

Decidir si existe una forma de asignar aulas de forma que se puedan dictartodas las materias respetando los horarios. Modelar como un problemade grafos.

12.- Construir cinco grafos con 8 v´ertices, todos de grado 3, de forma que cada dos de esos grafosno sean isomorfos.