Soluciones Ejercicios Capítulo 9.7 Matemáticas Discretas Johnsonbaugh 6 ed

1. Cuatro monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. Dibuje un árbol de decisiones para proporcionar un algoritmo que identifique, cuando mucho en dos pesadas, la moneda defectuosa (pero no necesariamente que determine si es más o menos pesada que las otras) usando sólo una balanza.


2. Demuestre que se requiere pesar al menos dos veces para resolver el problema del ejercicio 1.


3. Ocho monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. Dibuje un árbol de decisiones para proporcionar un algoritmo que identifique, cuando mucho en tres pesadas, la moneda defectuosa; y determine si es más pesada o más ligera que las otras usando sólo una balanza.


4. Doce monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. Dibuje un árbol de decisiones para proporcionar un algoritmo que identifique, cuando mucho en tres pesadas, la moneda defectuosa; y determine si es más pesada o más ligera que las otras usando sólo una balanza.


5. Diga qué está mal en el siguiente argumento que pretende demostrar que el acertijo de 12 monedas requiere al menos cuatro pesadas en el peor caso si se comienza por pesar cuatro monedas contra cuatro. Si se pesan cuatro monedas contra cuatro y están balanceadas, debemos detectar la moneda defectuosa de las cuatro restantes. Pero el análisis en esta sección demostró que detectar una moneda defectuosa entre cuatro requiere pesar al menos tres veces en el peor caso. Por lo tanto, en el peor caso, si se comienza pesando cuatro monedas contra otras cuatro, el acertijo de 12 monedas requiere al menos cuatro pesadas.


6. Trece monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. ¿Cuántas veces se requiere pesar en el peor caso para encontrar la moneda defectuosa y determinar si es más o menos pesada que las otras usando sólo una balanza? Pruebe su respuesta.


7. Resuelva el ejercicio 6 para el acertijo de 14 monedas.


8. (3n − 3)/2, n ≥ 2 monedas son idénticas en apariencia, pero una está defectuosa y es más pesada o más ligera que las otras, que pesan lo mismo. [Kurosaka] proporcionó un algoritmo para encontrar la moneda defectuosa y determinar, en n pesadas en el peor caso, si es más o menos pesada que las otras usando sólo una balanza. Pruebe que no es posible encontrar la moneda e identificar como más pesada o más ligera en menos de n pesadas.
 

9. Dé un algoritmo que ordene cuatro artículos usando cinco comparaciones en el peor caso.
 

10. Utilice árboles de decisiones para encontrar una cota inferior para el número de comparaciones requeridas para ordenar cinco artículos en el peor caso. Dé un algoritmo que use este número de comparaciones para ordenar cinco artículos en el peor caso.


11. Utilice árboles de decisiones para encontrar una cota inferior para el número de comparaciones requeridas para ordenar seis artículos en el peor caso. Dé un algoritmo que emplee este número de comparaciones para ordenar seis artículos en el peor caso.
 
 
Los ejercicios 12 al 18 se refieren al orden de torneo. Orden de torneo. Se tiene una secuencia

s1, ..., s2k
para ordenar en orden no decreciente. Se construirá un árbol binario con vértices terminales etiquetados s1, . . . , s2k. Un ejemplo es el siguiente



Trabajando de derecha a izquierda, se crea un padre para cada par y se etiqueta con el máximo número de hijos. Se continúa de esta manera hasta llegar a la raíz. En este punto, se ha encontrado el valor más grande, m. Para encontrar el segundo valor más grande, primero se escoge un valor v menor que todos los elementos de la sucesión. Se sustituye el vértice terminal w que contiene a m por v. Se etiquetan otra vez los vértices siguiendo la trayectoria de w a la raíz, como se indica. En este punto se ha encontrado el segundo valor más grande. Continúe hasta que la sucesión quede ordenada.



12. ¿Por qué es adecuado el nombre de “torneo”?
 

13. Dibuje los dos árboles que se crearían después del árbol adyacente cuando se aplica el orden de torneo.
 

14. ¿Cuántas comparaciones requiere el orden de torneo para encontrar el elemento más grande?


15. Demuestre que cualquier algoritmo que encuentra el valor más grande entre n elementos requiere al menos n−1 comparaciones.


16. ¿Cuántas comparaciones requiere el orden de torneo para encontrar el segundo elemento más grande?
 

17. Escriba el orden de torneo como un algoritmo formal.
 

18. Demuestre que si n es una potencia de 2, el orden de torneo requiere (n lg n) comparaciones.


19. Dé un ejemplo de una situación real (como la de la figura 9.7.1) que se pueda modelar como un árbol de decisiones. Dibuje el árbol de decisión.


20. Dibuje un árbol de decisiones que se pueda usar para determinar quién debe entregar una declaración federal de impuestos.
 

21. Dibuje un árbol de decisiones que dé una estrategia razonable para jugar blackjack (vea, por ejemplo [Ainslie]).

Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.6 Matemáticas Discretas Johnsonbaugh 6 ed

En los ejercicios 1 al 5, enumere el orden en el que los vértices se procesan usando los recorridos preorden, entreorden y postorden.



 
 


 
 
 


 
 


 
 

 
 

En los ejercicios 6 al 10, represente la expresión como un árbol binario y escriba sus formas de prefijo y posfijo.
6.  (A * B ) * (C - D)


7. ((A−C)∗ D) /(A+(B+ D))


8. (A∗ B +C ∗ D)−(A/B −(D+ E))


9. (((A+ B)∗C + D)∗ E)−((A+ B)∗C − D)


10. (A∗ B −C/D+ E)+(A− B−C − D∗ D)/(A+ B +C)
 

En los ejercicios 11 al 15, represente la expresión en posfijo como un árbol binario y escriba la forma de prefijo, la forma usual de entrefijo y la forma de entrefijo con paréntesis completos de la expresión.

11. AB + C-


12. ABC +-


13. ABCD +* /E-
 

14. ABC**CDE+/-

15. AB+CD*EF/--A*
 
En los ejercicios 16 al 21, encuentre el valor de la expresión en posfijo si A=1, B=2, C=3 y D=4.

16. ABC+-

17. AB+C-

18. AB+CD*AA/--B*

19. ABC**ABC++-

20. ABAB*+*D*

21. ADBCD*-+*

22. Demuestre, por ejemplo, que los árboles binarios distintos con vértices A, B y C pueden tener la misma lista de preorden A B C .


23. Demuestre que hay un árbol binario único con seis vértices cuya lista de vértices de preorden es A B C E F D y cuya lista de vértices de entreorden es A C F E B D.


24. Escriba un algoritmo que reconstruya el árbol binario dados sus ordenamientos de preorden e entreorden.


25. Dé ejemplos de árboles binarios diferentes, B1 y B2, cada uno con dos vértices, donde la lista de vértices de preorden de B1 es igual a la lista de preorden de B2 y la lista de vértices de postorden de B1 es igual a la lista de postorden de B2.


26. Sean P1 y P2 permutaciones de A B C D E F. ¿Existe un árbol binario con vértices A, B, C, D, E y F cuya lista de preorden sea P1 y cuya lista de entreorden sea P2? Explique.


27. Escriba un algoritmo recursivo que imprima el contenido de los vértices terminales de un árbol binario de izquierda a derecha.
 

28. Escriba un algoritmo recursivo que intercambie todos los hijos izquierdos y derechos de un árbol binario.


29. Escriba un algoritmo recursivo que inicialice cada vértice de un árbol binario con el número de sus descendientes.

En los ejercicios 30 y 31, toda expresión implica sólo los operandos A, B, . . . , Z y las operaciones +, −, *, /.
 

30. Dé una condición necesaria y suficiente para que una cadena de símbolos sea una expresión en posfijo válida.
 

31. Escriba un algoritmo que, dada la representación por árbol binario de una expresión, produzca la forma de entrefijo con paréntesis completos de la expresión.
 

32. Escriba un algoritmo que imprima los caracteres y sus códigos dado un árbol de codificación de Huffman (vea el ejemplo 9.1.8). Suponga  ga que cada vértice terminal almacena un carácter y su frecuencia.
 
 
Utilice las siguientes definiciones en los ejercicios 33 al 38.
Sea G = (V, E) un gráfica no dirigida simple. Una cubierta de los vértices de G es un subconjunto V de V tal que para cada arista (v, w) ∈E, ya sea v∈V o w∈V . El tamaño de la cubierta de vértices V es el número de vértices en V . Una cubierta de vértices óptima es una cubierta de vértices de tamaño mínimo. Un conjunto ajeno de aristas para G es un subconjunto E de E tal que para cada par de aristas distintas e1=(v1, w1)y e=(v2, w2) en E , se tiene

{v1, w1}∩{v2, w2}=∅

33. Pruebe que para cada n, existe una gráfica conexa con n vértices que tiene una cubierta de vértices de tamaño 1.


34. Demuestre que el tamaño de una cubierta de vértices óptima de la gráfica completa con n vértices es n−1.


35. El tamaño de una cubierta de vértices óptima de una gráfica con n vértices, ¿puede ser igual a n? Explique su respuesta.


36. Escriba un algoritmo que encuentre una cubierta de vértices óptima de un árbol T=(V, E) cuyo tiempo en el peor caso es (|E|).


37. Demuestre que si V es cualquier cubierta de vértices de una gráfica G y E es cualquier conjunto ajeno de aristas de G, entonces |E |≤|V |.


38. Dé un ejemplo de una gráfica conexa en la que para cada cubierta de vértices V y cada conjunto ajeno de aristas E , se tiene |E | < |V |. Pruebe que su ejemplo tiene la propiedad requerida.


39. Muestre cómo un árbol binario con n aristas se puede codificar como una cadena de n+1 unos y n+1 ceros donde, si se lee de izquierda a derecha, el número de ceros nunca excede al número de unos. Demuestre que cada cadena de este tipo representa un árbol binario. Sugerencia: Considere un recorrido preorden del árbol binario en el que un 1 significa que una arista está presente, y un 0 significa que una arista está ausente. Agregue un uno adicional al principio de la cadena, y elimine el último cero.
 
 

Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.5 Matemáticas Discretas Johnsonbaugh 6 ed


1. Coloque las palabras FOTO SOBRE ARRIBASIETE YAANTES OBSERVA FELIZ BARATO FOMENTO, en el orden en el que aparecen, en un árbol de búsqueda binaria.


2. Escriba un algoritmo formal de búsqueda en un árbol de búsqueda binaria.


3. Escriba un algoritmo que almacene n palabras diferentes en un árbol de búsqueda binaria Tde altura mínima. Demuestre que el árbol T* obtenido, como se describe en el texto, tiene altura     lg(n+1)


4. ¿Falso o verdadero? Sea T un árbol binario. Si para cada vértice v en T el dato en v es mayor que el dato en el hijo izquierdo de v, y el dato en v es menor que el dato en el hijo derecho de v, entonces T es un árbol de búsqueda binaria. Explique.

En los ejercicios 5 al 7, dibuje una gráfica que tenga las propiedades indicadas o explique por qué no existe la gráfica.

5. Árbol binario completo; 4 vértices internos; 5 vértices terminales
 
 
6. Árbol binario completo; altura =3; 9 vértices terminales
 

7. Árbol binario completo; altura =4; 9 vértices terminales

8. Un árbol m-ario completo es un árbol con raíz tal que todo padre tiene m hijos ordenados. Si T es un árbol m-ario completo con i vértices internos, ¿cuántos vértices tiene T? ¿Cuántos vértices terminales tiene T? Pruebe sus resultados.


9. Proporcione un algoritmo para construir un árbol binario completo con n > 1 vértices terminales.


10. Proporcione un algoritmo recursivo para insertar una palabra en un árbol de búsqueda binaria.


11. Encuentre la altura máxima de un árbol binario completo que tiene t vértices terminales.


12. Escriba un algoritmo que pruebe si un árbol binario en el que se almacenan datos en los vértices es un árbol de búsqueda binaria.


13. Sea T un árbol binario completo. Sea I la suma de las longitudes de las trayectorias simples de la raíz a los vértices internos. I se llama longitud de trayectoria interna. Sea E la suma de las longitudes de las trayectorias simples de la raíz a los vértices terminales. Ese llama longitud de trayectoria externa. Pruebe que si Ttiene n vértices terminales, entonces E=I−2n.

Un árbol binario T está balanceado si para cada vértice v en T, las alturas de los subárboles izquierdo y derecho de v difieren cuando mucho en 1. (Aquí, la altura de un árbol vacío se define como −1).
 
 
Establezca si cada árbol en los ejercicios 14 al 17 está balanceado o no.



 
 

 
 
 
 

 
 

 
 
En los ejercicios 18 al 20, Nh se define como el número mínimo de vértices en un árbol binario balanceado de altura h y f1, f2, . . . denota la sucesión de Fibonacci.

18. Demuestre que N0 =1, N1 =2 y N2 =4.


19. Demuestre que Nh =1 +Nh−1 +Nh−2, para h≥0.


20. Demuestre que Nh =fh+3 −1, para h≥0.


21. Demuestre que la altura h de un árbol binario balanceado de n vértices satisface h=O(lg n). Este resultado indica que el tiempo de búsqueda, en el peor caso, en un árbol de búsqueda binaria balanceado de n vértices es O(lg n).


22. Pruebe que si un árbol binario de altura h tiene n≥1 vértices, entonces lg n < h + 1. Este resultado, junto con el ejercicio 21, muestra que el tiempo de búsqueda en el peor caso en un árbol de búsqueda binaria balanceado de n vértices es (lg n).



Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.4 Matemáticas Discretas Johnsonbaugh 6 ed

En los ejercicios 1 al 5, encuentre el árbol de expansión mínima dado por el algoritmo 9.4.3 para cada gráfica.


 
 



 
 

 
 

 
 


6. Demuestre que el algoritmo 9.4.3 examina (n3) aristas en el peor caso.
 
 
Los ejercicios 7 al 9 se refieren a la versión alternativa del algoritmo de Prim (algoritmo 9.4.6).
Algoritmo 9.4.6
Versión alternativa del algoritmo de Prim
Este algoritmo encuentra un árbol de expansión mínima en un gráfica G conexa ponderada. En cada paso, algunos vértices tienen etiquetas temporales y otros tienen etiquetas permanentes. La etiqueta de un vértice i se denota por Li. Entrada: Gráfica conexa ponderada con vértices 1, . . . , n y vértice inicial s. Si (i, j) es una arista, w(i, j) es igual al peso de (i, j); si (i, j) no es una arista, w(i, j) es igual a ∞ (un valor mayor que cualquier peso real) Salida: Árbol de expansión mínima T


7. Muestre la manera en que el algoritmo 9.4.6 encuentra un árbol de expansión mínima para las gráficas de los ejercicios 1 al 5.


8. Demuestre que el algoritmo 9.4.6 examina (n2) aristas en el peor caso.


9. Pruebe que el algoritmo 9.4.6 es correcto; es decir, al terminar el algoritmo, T es un árbol de expansión mínima.


10. Sea G una gráfica conexa ponderada, sea v un vértice en G y sea e la arista con peso mínimo incidente en v. Demuestre que e está contenida en algún árbol de expansión mínima.


11. Sea G una gráfica conexa ponderada y sea v un vértice en G. Suponga que los pesos de las aristas incidentes en v son distintos. Sea e la arista con peso mínimo incidente en v. ¿Debe e estar contenida en todo árbol de expansión mínima?


12. Demuestre que cualquier algoritmo que encuentra un árbol de expansión mínima en Kn, cuando todos los pesos son iguales, debe examinar toda arista en Kn.


13. Demuestre que si todos los pesos en una gráfica conexa G son diferentes, G tiene un árbol de expansión mínima.


En los ejercicios 14 al 16, decida si la afirmación es falsa o verdadera. Si es verdadera, pruébela; de otra manera, dé un contraejemplo. En cada ejercicio, G es una gráfica conexa y ponderada.

14. Si todos los pesos en G son distintos, los árboles de expansión de G diferentes tienen pesos diferentes.


15. Si e es una arista en G cuyo peso es menor que el peso de cada tercera arista, e está en todo árbol de mínima expansión de G.


16. Si T es un árbol de expansión mínima de G, existe un etiquetado de los vértices de G de manera que el algoritmo 9.4.3 produce T.

 17. Sea G una gráfica conexa ponderada. Demuestre que si, mientras sea posible, se elimina una arista de G con peso máximo y cuya eliminación no desconecta a G, el resultado es un árbol de expansión mínima para G.

18. Escriba un algoritmo que encuentre un árbol de expansión mínima en una gráfica conexa ponderada.


19. Pruebe que su algoritmo del ejercicio 18 es correcto. El algoritmo de Kruskal encuentra un árbol de expansión mínimo en una gráfica G conexa ponderada que tiene n vértices como sigue. La gráfica Tinicialmente consiste en los vértices de G y ninguna arista. En cada iteración, se agrega una arista e a Tcon peso mínimo que no completa un ciclo en T. Cuando T tiene n −1 aristas, se detiene.
 

20. Establezca formalmente el algoritmo de Kruskal.
 

21. Muestre cómo el algoritmo de Kruskal encuentra árboles de expansión mínima para las gráficas de los ejercicios 1 al 5.


22. Demuestre que el algoritmo de Kruskal es correcto; es decir, al terminar el algoritmo de Kruskal, T es un árbol de expansión mínima.


23. Sea V un conjunto de n vértices y sea s una “función de disimilitud” en V×V (vea el ejemplo 8.1.7). Sea G la gráfica ponderada completa que tiene vértices V y pesos w(vi, vj) =s(vi, vj). Modifique el algoritmo de Kruskal de manera que agrupe datos en clases. Esta modificación se conoce como método del vecino más cercano (vea [Gosel]).
 

Los ejercicios 24 al 30 se refieren a la siguiente situación. Suponga que tenemos timbres de varias denominaciones y queremos elegir el mínimo número de timbres para completar una cantidad dada de importe postal. Considere un algoritmo ambicioso que selecciona timbres escogiendo todos los que puede de la denominación más grande, después todos los que puede de la denominación siguiente más grande, y así sucesivamente.


24. Demuestre que si las denominaciones disponibles son 1, 8 y 10 centavos, el algoritmo no siempre produce el menor número de timbres para completar un importe postal dado.


25. Demuestre que si las denominaciones disponibles son 1, 5 y 25 centavos, el algoritmo produce el menor número de timbres para completar un importe dado.


26. Encuentre enteros positivos a1 y a2 tales que a1 > 2a2 > 1, a2 no divide a a1 y el algoritmo, con denominaciones disponibles 1, a1, a2, no siempre produce el menor número de timbres para completar el importe postal.


27. Encuentre enteros positivos a1 y a2 tales que a1 > 2a2 > 1, a2 no divide a a1 y el algoritmo, con denominaciones disponibles 1, a1, a2, produce el menor número de timbres para completar cualquier importe postal dado. Pruebe que sus valores en realidad dan una solución óptima.


28. Suponga que las denominaciones disponibles son
1=a1 < a2 < ···< an.
Demuestre, dando un contraejemplo, que la condición
ai ≥2ai−1 −ai−2,3 ≤i ≤n,

no es necesaria ni suficiente para que el algoritmo ambicioso sea óptimo.


29. Demuestre que el algoritmo ambicioso es óptimo para las denominaciones
1=a1 < a2 < ···< am

si y sólo si ese algoritmo es óptimo para todas las denominaciones menores que am−1+am. (Este resultado se debe a William Seaman).


30. Demuestre que la cota am−1 + am en el ejercicio 29 no puede ser menor.
 
 

Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.3 Matemáticas Discretas Johnsonbaugh 6 ed

1. Use la búsqueda a lo ancho (algoritmo 9.3.6) con el orden de vértices hgfedcba para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.

2. Use la búsqueda a lo ancho (algoritmo 9.3.6) con el orden de vértices hfdbgeca para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.


3. Use la búsqueda a lo ancho (algoritmo 9.3.6) con el orden de vértices chbgadfe para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.


4. Use la búsqueda a profundidad (algoritmo 9.3.7) con el orden de vértices hgfedcba para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.


5. Use la búsqueda a profundidad (algoritmo 9.3.7) con el orden de vértices hfdbgeca para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.


6. Use la búsqueda a profundidad (algoritmo 9.3.7) con el orden de vértices dhcbefag para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.

En los ejercicios 7 al 9, encuentre un árbol de expansión para cada gráfica.












 
 
10. Demuestre que no hay solución a los problemas de dos y tres reinas.


11. Encuentre una solución a los problemas de cinco y seis reinas.


12. ¿Falso o verdadero? Si G es una gráfica conexa y T es un árbol de expansión para G, existe un orden de los vértices de G tal que el algoritmo 9.3.6 produce T como una árbol de expansión. Si es verdadero, pruébelo; de otra manera, proporcione un contraejemplo.


13. ¿Falso o verdadero? Si G es una gráfica conexa y T es un árbol de expansión para G, existe un orden de los vértices de G tal que el algoritmo 9.3.7 produce T como un árbol de expansión. Si es verdadero, pruébelo; de otra manera, proporcione un contraejemplo.


14. Muestre, mediante un ejemplo, que el algoritmo 9.3.6 puede producir árboles de expansión idénticos para una gráfica conexa G a partir de dos ordenamientos de los vértices de G.
 

 15. Muestre, mediante un ejemplo, que el algoritmo 9.3.7 puede producir árboles de expansión idénticos para una gráfica conexa G a partir de dos ordenamientos de los vértices de G.


16. Pruebe que el algoritmo 9.3.6 es correcto.


17. Pruebe que el algoritmo 9.3.7 es correcto.


18. ¿En qué condiciones una arista en una gráfica conexa G está contenida en todos los árboles de expansión de G?


19. Sean T y T dos árboles de expansión de una gráfica conexa G. Suponga que una arista x está en T pero no en T . Demuestre que existe una arista y en T pero no en T tal que (T − {x})∪{y} y (T −{y}) ∪ {x}) son árboles de expansión de G.


20. Escriba un algoritmo basado en la búsqueda a lo ancho que encuentre la longitud mínima de cada trayectoria en una gráfica no ponderada de un vértice fijo v a todos los demás.


21. Sea Guna gráfica ponderada en la que el peso de cada arista es un entero positivo. Sea G la gráfica obtenida de G al sustituir cada arista




en G con peso k por k aristas no ponderadas en serie:




 Demuestre que el algoritmo de Dijkstra para encontrar la longitud mínima de cada trayectoria en la gráfica ponderada G desde un vértice fijo v a todos lo demás (algoritmo 8.4.1) y realizar la búsqueda a lo ancho en una gráfica no ponderada G comenzando en el vértice v son, de hecho, el mismo proceso.
 

22. Sea Tun árbol de expansión para una gráfica G. Demuestre que si una arista en G, pero no en T, se agrega a T, se produce un ciclo único. Un ciclo como el descrito en el ejercicio 22 se llama ciclo fundamental. La matriz del ciclo fundamental de una gráfica G tiene renglones indexados según los ciclos fundamentales de G respecto a un árbol de expansión Tpara G y sus columnas indexadas según las aristas de G. El elemento ij es 1 si la arista j está en el i-ésimo ciclo fundamental y 0 de otra manera. Por ejemplo, la matriz del ciclo fundamental de la gráfica G de la figura 9.3.1 relativa al árbol de expansión mostrado en la figura 9.3.1 es









Encuentre la matriz del ciclo fundamental de cada gráfica. El árbol de expansión que se usará está dibujado con línea continua.







 



 


26. Escriba un algoritmo de búsqueda a profundidad para probar si una gráfica es conexa.


27. Escriba un algoritmo de búsqueda a profundidad para probar si una gráfica es conexa.
 

28. Escriba un algoritmo de búsqueda a lo largo para encontrar todas las soluciones al problema de las cuatro reinas.
 
 
Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.2 Matemáticas Discretas Johnsonbaugh 6 ed

Responda las preguntas en los ejercicios 1 al 6 para el árbol en la figura 9.2.1.

1. Encuentre el padre de Poseidón.

2. Encuentre los ancestros de Eros.

3. Encuentre los hijos de Urano.

4. Encuentre los descendientes de Zeus.

5. Encuentre los hermanos de Ares.

6. Dibuje el subárbol con raíz en Afrodita.
 
Responda las preguntas en los ejercicios 7 al 15 para el siguiente árbol.


 


7. Encuentre los padres de c y h.
 

8. Encuentre los ancestros de c y j.
 

9. Encuentre los hijos de d y e.

10. Encuentre los descendientes de c y e.

11. Encuentre los hermanos de f y h.


12. Encuentre los vértices terminales.


13. Encuentre los vértices internos.
 

14. Dibuje el subárbol con raíz en j.
 

15. Dibuje el subárbol con raíz en e.
 

16. Responda a las preguntas en los ejercicios 7 al 15 para el siguiente árbol.












17. ¿Qué puede decir de dos vértices en un árbol con raíz que tienen el mismo padre?
 

18. ¿Qué puede decir de dos vértices en un árbol con raíz que tienen los mismos ancestros?


19. ¿Qué puede decir de un vértice en un árbol que no tiene ancestros?


20. ¿Qué pude decir de dos vértices en un árbol con raíz que tienen un descendiente en común?

21. ¿Qué puede decir de un vértice en un árbol con raíz que no tiene descendientes?



En los ejercicios 22 al 26, dibuje una gráfica que tenga las propiedades indicadas o explique por qué no existe tal gráfica.

22. Seis aristas; ocho vértices
 

23. Acíclica; cuatro aristas, seis vértices
 

24. Árbol; todos los vértices de grado 2

25. Árbol; seis vértices que tienen 1, 1, 1, 1, 3, 3 grados


26. Árbol; cuatro vértices internos, seis vértices terminales


27. Explique por qué, si se permiten ciclos de longitud 0, una gráfica que consiste en un solo vértice y ninguna arista no es acíclica.


28. Explique por qué, si se permite que los ciclos repitan aristas, una gráfica que consiste en una sola arista y dos vértices no es acíclica.

29. La gráfica conexa mostrada tiene una trayectoria simple única de cualquier vértice a cualquier otro, pero no es un árbol. Explique por qué.



Un bosque es una gráfica simple sin ciclos.


30. Explique por qué un bosque es una unión de árboles.


31. Si un bosque F  consiste en m árboles y tiene n vértices, ¿cuántas aristas tiene F?
 

32. Si P1=(v0, . . . , vn) y P2=(w0, . . . , wm) son dos trayectorias simples de a a b diferentes, en una gráfica simple G, ¿es

(v0, ..., vn =wm, wm−1, ..., w1, w0)

necesariamente un ciclo? Explique su respuesta. (Este ejercicio es relevante para el último párrafo de la demostración del Teorema 9.2.3).


33. Demuestre que una gráfica Gcon nvértices y menos de n−1 aristas no es conexa.


34. Pruebe que T es un árbol si y sólo si T es conexa y cuando se agrega una arista entre cualesquiera dos vértices, se crea exactamente un ciclo.


35. Demuestre que si G es un árbol, todo vértice de grado 2 o más es un punto de articulación. (“Punto de articulación” se definió en el ejercicio 55, de la sección 8.2).


36. Dé un ejemplo para demostrar que el inverso del ejercicio 35 es falso, incluso si se supone que G es conexa.


Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.1 Matemáticas Discretas Johnsonbaugh 6 ed

¿Cuáles gráficas en los ejercicios 1 al 4 son árboles? Explique.



 






 
 



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
 
 
22. ¿Qué factores además de la cantidad de memoria usada deben considerarse cuando se elige un código, como ASCII o Huffman, para representar caracteres en una computadora?

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.


Etiquetas: , , ,
Suscribirse a: Comentarios (Atom)