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.
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.
