5. ¿Para qué valores de m y n la gráfica bipartita completa sobre m y n vértices es un árbol?
6. ¿Para qué valores de n la gráfica completa sobre n vértices es un árbol?
7. ¿Para qué valores de n es el cubo-n un árbol?
8. Encuentre el nivel de cada vértice en el árbol que sigue.
9. Encuentre la altura del árbol del ejercicio 8.
10. Dibuje el árbol T de la figura 9.1.5 como un árbol con raíz en a. ¿Cuál es la altura del árbol obtenido?
11. Dibuje el árbol T de la figura 9.1.15 como un árbol con raíz en b. ¿Cuál es la altura del árbol obtenido?
12. Dé un ejemplo similar al ejemplo 9.1.5 de un árbol que se usa para especificar relaciones de jerarquía.
13. Dé un ejemplo diferente al ejemplo 9.1.5 de un árbol de definición jerárquica. Decodifique cada cadena de bits que usa el código Huffman dado.
14. 011000010
15. 01110100110
16. 01111001001110
17. 1110011101001111
Codifique cada palabra usando el código Huffman anterior.
18. DEN
19. NEED
20. LEADEN
21. PENNED
23. ¿Qué técnicas además del uso de códigos Huffman se puede usar para ahorrar memoria cuando se almacena texto?
24. Construya un código Huffman óptimo para el conjunto de letras en la tabla.
25. Construya un código de Huffman óptimo para el conjunto de letras en la tabla
26. Use el código desarrollado en el ejercicio 25 para codificar las siguientes palabras (que tienen frecuencias consistentes con la tabla del ejercicio 25):
BUS, CUPS, MUSH, PUSS, SIP, PUSH, CUSS, HIP, PUP, PUPS, HIPS.
27. Construya dos árboles de codificación de Huffman óptimos para la tabla del ejercicio 24, de diferentes alturas.
28. Construya un código Huffman óptimo para el conjunto de letras en la tabla.
Get 9.1.28 exercise solution
29. El profesor Gig A. Byte necesita almacenar texto formado con los caracteres A, B, C, D, E, que ocurren con las siguientes frecuencias:
El profesor Byte sugiere usar los códigos de longitud variable
los cuales, asegura, almacenan texto en menos espacio que el usado por un código Huffman óptimo. ¿Está en lo correcto el profesor? Explique su respuesta.
30. Demuestre que cualquier árbol con dos vértices o más tiene un vértice de grado 1.
31. Demuestre que un árbol es una gráfica plana.
32. Demuestre que un árbol es una gráfica bipartita.
33. Demuestre que los vértices de un árbol se pueden colorear con dos colores de manera que cada arista incida en vértices de diferentes colores. La excentricidad de un vértice v en un árbol T es la longitud máxima de una trayectoria simple que comienza en v.
34. Encuentre la excentricidad de cada vértice en el árbol de la figura 9.1.5. Un vértice v en un árbol T es un centro para T si la excentricidad de v es mínima.
35. Encuentre el centro o centros del árbol de la figura 9.1.5.
36. Demuestre que un árbol tiene uno o dos centros.
37. Demuestre que si un árbol tiene dos centros, éstos son adyacentes.
38. Defina el radio r de un árbol usando los conceptos de excentricidad y centro. El diámetro d de una gráfica se definió en el ejercicio 70, sección 8.2. ¿Es cierto siempre, de acuerdo con su definición de radio, que 2r=d? Explique su respuesta.
39. Dé un ejemplo de un árbol T que no satisface la siguiente propiedad: Si v y w son vértices en T, existe una trayectoria única de v a w.
