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