MA265 Cadenas de Markov [Diapo]

Matemática Discreta Ejercicios de clase de Árboles Dirigidos 1. Sea 𝐴 = {𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 4 , 𝑣 5 , 𝑣 6 , 𝑣 7 , 𝑣 8 , 𝑣 9 , 𝑣 10 } y 𝑇 = {(𝑣 2 , 𝑣 3 ), (𝑣 2 , 𝑣 1 ), (𝑣 4 , 𝑣 5 ), (𝑣 4 , 𝑣 6 ), (𝑣 5 , 𝑣 8 ), (𝑣 6 , 𝑣 7 ), (𝑣 4 , 𝑣 2 ), (𝑣 7 , 𝑣 9 ), (𝑣 7 , 𝑣 10 )} Muestre que T es un árbol e identifique qué tipo de n-árbol es, su raíz, altura y hojas. 2. Dado el árbol T cuyos elementos son: 𝑇 = { (𝐵, 𝐶), (𝐹, 𝐸), (𝐹, 𝐼), (𝐹, 𝑀), (𝐴, 𝐺), (𝐴, 𝐻), (𝐶, 𝐽), (𝐷, 𝐵), (𝐷, 𝐹), (𝐵, 𝐴), (𝐼, 𝐾)(𝐼, 𝐿), (𝑀, 𝑂)(𝑀, 𝑃), (𝑃, 𝑄) } (a) Trace el dígrafo del árbol T ordenado indicando la raíz y el tipo de n - árbol. (b) Trace el dígrafo del árbol binario posicional 𝐵(𝑇) formado a partir del árbol T ordenado. (c) Verifique que el contenido de los arreglos LEFT, DATA y RIGHT es: Índice LEFT DATA RIGHT 1 5 2 8 A 4 3 2 B 7 4 11 C 0 5 3 D 0 6 0 E 10 7 6 F 0 8 0 G 9 9 0 H 0 10 12 I 14 11 0 J 0 12 0 K 13 13 0 L 0 14 15 M 0 15 0 O 16 16 17 P 0 17 0 Q 0 3. Dado el árbol T cuyos elementos son: 𝑇 = { (𝑎, 𝑙), (𝑏, 𝑐), (𝑏, 𝑑), (𝑐; 𝑎), (𝑐, 𝑒), (𝑐, 𝑓), (𝑑, ℎ), (𝑑, 𝑖), (𝑓, 𝑚), (𝑖, 𝑗), (𝑖, 𝑘), (𝑖, 𝑛), (ℎ, 𝑔), (𝑖, 𝑝) } (a) Trace el dígrafo del árbol T ordenado indicando la raíz y el tipo de n - árbol. (b) Trace el dígrafo del árbol binario etiquetado ) ( T B formado a partir del árbol T ordenado. (c) Determine el contenido de los arreglos LEFT, DATA y RIGHT. Matemática Discreta 2 4. Dado el arreglo LEFT, DATA y RIGHT : (a) Trace el dígrafo del árbol binario posicional ) ( T B representado por el arreglo LEFT, DATA y RIGHT mostrado . (b) Trace el dígrafo del árbol T ordenado indicando la raíz y el tipo de n - árbol. 5. Dado el árbol T cuyos elementos son: 𝑇 = { (1; 12), (2; 3), (2; 4), (3; 1), (3; 5), (3; 6), (4; 8), (4; 9), (6; 13), (9; 10), (9; 11), (9; 14), (8; 7), (9; 15) } (a) Trace el dígrafo del árbol T ordenado indicando la raíz y el tipo de n - árbol. (b) Trace el dígrafo del árbol binario etiquetado ) ( T B formado a partir del árbol T ordenado. (c) Determine el contenido de los arreglos LEFT, DATA y RIGHT. 6. Dado el árbol T cuyos elementos son: 𝑇 = {(𝐸, 𝐵), (𝐸, 𝐶), (𝐸, 𝐹), (𝐵, 𝐴), (𝐵, 𝐺), (𝐶, 𝐾), (𝐹, 𝐻), (𝐹, 𝐼), (𝐹, 𝐽), (𝐴, 𝐿), (𝐻, 𝑀)} a. Trace el dígrafo del árbol 𝑇 ordenado indicando la raíz y el tipo de 𝑛 - árbol. b. Trace el dígrafo del árbol binario posicional 𝐵(𝑇) formado a partir del árbol 𝑇 ordenado. c. Determine el contenido de los arreglos LEFT, DATA y RIGHT. ÍNDICE LEFT DATA RIGHT 1 7 2 9 A 4 3 0 B 6 4 3 C 8 5 0 D 10 6 5 E 0 7 2 F 0 8 0 G 0 9 12 H 11 10 0 I 0 11 0 J 0 12 0 K 0