1CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

A

B C

E F G

D H I

IZQ DERINFO

Almacena la dirección del subárbol izquierdo. Almacena la información

del nodo.

Almacena la dirección del subárbol derecho.

A

B C

E F G

HDI

/

/ / / // /

///

1

2

3

4 5

6

7 8

9

2 6

3 7 8

4 5 9

Ejercicios de Árboles y Grafos

1. Dado el siguiente árbol binario.

a) Representar el árbol mediante listas enlazadas.

La representación de árboles mediante listas enlazadas consiste en representar los nodos del árbol binario como registros que tendrán a lo menos 3 campos como se muestra a continuación.

Luego, la representación binaria del árbol del enunciado será.

2CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

b) Calcular los recorridos preorden, inorden, postorden.

- Recorrido Preorden (PID): Consiste en examinar el nodo raíz (o padre), luego recorrer el subárbol izquierdo en forma preorden; y finalmente, recorrer el subárbol derecho en recorrido preorden.

Desarrollo, sea G el árbol binario:G = GA = AGBGC = ABGEGC = ABEGDGHGC = ABEDGHGC = ABEDHGC = ABEDHCGFGG =

ABEDHCFGG = ABEDHCFGGI = ABEDHCFGI→ G = ABEDHCFGI

- Recorrido Inorden (IPD): Consiste en recorrer el subárbol izquierdo en forma inorden, luego examinar el nodo raíz (o padre); y finalmente, recorrer el subárbol derecho en recorrido inorden.

Desarrollo:G = GA = GBAGC = BGEAGC = BGDEGHAGC = BDEGHAGC = BDEHAGC = BDEHAGFCGG =

BDEHAFCGG = BDEHAFCGGI = BDEHAFCGI

→ G = BDEHAFCGI

- Recorrido Postorden (IDP): Consiste en recorrer el subárbol izquierdo en forma postorden, luego recorrer el subárbol derecho en recorrido postorden; y finalmente examinar el nodo raíz (o padre).

Desarrollo:G = GA = GBGCA = GEBGCA = GDGHEBGCA = DGHEBGCA = DHEBGCA = DHEBGFGGCA =

DHEBFGGCA = DHEBFGIGCA = DHEBFIGCA→ G = DHEBFIGCA

2. Dado el siguiente array:

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

3CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

A

B F

E

C DD G

3

/ ////

1

2

5

7

6

3 4

2 6

4 7 /

/ /

5

A

B F

E

GC D

Mediante listas enlazadas:

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

preorden ABCDEFG y en inorden CDBEAGF

a) Dibujar el árbol binario Como en el recorrido preorden el nodo raíz siempre aparece al inicio del recorrido,

entonces asumimos que A es el nodo raíz.

A

B F

D

C E G

4CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

b) Determinar el recorrido en postorden

Desarrollo:G = GA = GBGFA = GCGEBGFA = GDCGEBGFA = DCGEBGFA = DCEBGFA = DCEBGGFA =

DCEBGFA → G = DCEBGFA

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.

Nodo Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6

a (0; a) --- --- --- --- ---

b (3; a) (3; a) --- --- --- ---

c ∞ (4; b) (4; b) --- --- ---

d (6; a) (6; a) (6; a) (5; f) (5; f) ---

e ∞ ∞ ∞ ∞ ∞ ∞

f (5; a) (4; b) (4; b) (4; b) --- ---

S D P

a T 0

b T 3 a

c T 4 b

d T 5 f

e --- ---

f T 4 b

5CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

Nodo Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Paso 7

a (0; a) --- --- --- --- --- ---

b (2; a) (2; a) --- --- --- --- ---

c ∞ (4; b) (4; b) (4; b) --- --- ---

d (2; a) (2; a) (2; a) --- --- --- ---

e ∞ ∞ ∞ ∞ ∞ ∞ ∞

f ∞ ∞ (5; e) (5; e) (5; e) ---

g ∞ ∞ ∞ ∞ ∞ ∞ ∞

h ∞ ∞ ∞ ∞ ∞ ∞ ∞

i ∞ ∞ (5; e) (5; e) (5; e) (5; e) ---

s ∞ ∞ ∞ ∞ ∞ ∞ ∞

t ∞ ∞ ∞ (8; c) (8; c) (8; c) (8; c)

6CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

S D Pa T 0b T 2 ac T 4 bd --- --- ---e T 2 af T 5 eg --- --- ---h --- --- ---i T 5 es --- --- ---t T 8 c

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.

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.

a b c d ea --- 1 ∞ ∞ ∞b ∞ --- 2 ∞ ∞c ∞ ∞ --- 2 4d ∞ 1 3 --- ∞e ∞ ∞ ∞ 5 ---

Primera iteracióna b c d e

a --- 1 ∞ ∞ ∞b ∞ --- 2 ∞ ∞c ∞ ∞ --- 2 4d ∞ 1 3 --- ∞e ∞ ∞ ∞ 5 ---

Segunda iteración

a b c d ea --- 2 3 4 5b 1 --- 3 4 5c 1 2 --- 4 5d 1 2 3 --- 5e 1 2 3 4 ---

a b c d ea --- 2 3 4 5b 1 --- 3 4 5c 1 2 --- 4 5d 1 2 3 --- 5e 1 2 3 4 ---

7CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

a b c d ea --- 1 3 ∞ ∞b ∞ --- 2 ∞ ∞c ∞ ∞ --- 2 4d ∞ 1 3 --- ∞e ∞ ∞ ∞ 5 ---

Tercera iteracióna b c d e

a --- 1 3 5 7b ∞ --- 2 4 6c ∞ ∞ --- 2 4d ∞ 1 3 --- 7e ∞ ∞ ∞ 5 ---

Cuarta iteracióna b c d e

a --- 1 3 5 10b ∞ --- 2 4 6c ∞ 3 --- 2 4d ∞ 1 3 --- 7e ∞ 6 8 5 ---

Quinta iteracióna b c d e

a --- 1 3 5 7b ∞ --- 2 4 6c ∞ 3 --- 2 4d ∞ 1 3 --- 7e ∞ 6 8 5 ---

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

G Conjunto de grafos dirigidos y etiquetadosM Conjunto de nodos de los grafosE Conjunto de valores de las etiquetas en las aristasN Conjunto de naturales

a b c d ea --- 2 2 4 5b 1 --- 3 4 5c 1 2 --- 4 5d 1 2 3 --- 5e 1 2 3 4 ---

a b c d ea --- 2 3 3 3b 1 --- 3 3 3c 1 2 --- 4 5d 1 2 3 --- 3e 1 2 3 4 ---

a b c d ea --- 2 3 4 5b 1 --- 3 4 5c 1 4 --- 4 5d 1 2 3 --- 5e 1 4 4 4 ---

a b c d ea --- 2 3 4 5b 1 --- 3 4 5c 1 2 --- 4 5d 1 2 3 --- 5e 1 2 3 4 ---

8CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

1

5

7

3

8

2

6

4

B Conjunto de booleanosU 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 sus respectivos 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 dictar todas las materias respetando los horarios. Modelar como un problema de grafos.

Modelamos el siguiente problema, considerando como nodos a las materias y las aristas indicarán que luego de ese curso puede llevarse el otro al que apunta.

Nodo Curso1 Álgebra2 Análisis I3 Análisis II4 Lineal5 Análisis III6 Complejo7 Operativa8 Estadística

9CIENCIAS DE LA COMPUTACIÓN II - (2012 – I)

UNMSM - FCM – EAP. CC

Para saber si se puede dictar los cursos en cuatro aulas respetando los horarios, debemos encontrar 4 caminos diferentes en el grafo.

AULA I AULA II AULA III AULA IVÁlgebra Análisis III

ComplejoEstadística

Análisis IAnálisis II

Lineal¿Operativa?

En por lo menos una aula, existe cruce de horarios. Por lo tanto, no se pueden dictar todos los cursos respetando los horarios.

12. Construir cinco grafos con 8 vértices, todos de grado 3, de forma que cada dos de esos grafos no sean isomorfos.

* Isomorfismo de grafos: dos grafos son isomorfos si sus matrices de adyacencia son iguales.