Abrir menú principal

Cuba-Wiki β

Final del 30/07/15 (Algoritmos III)

Ejercicio 1Editar

Dado un subconjunto Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S = \{s_1, s_2 \dots s_n\}} y un entero Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k} , diseñar un algoritmo que devuelva si existe un subconjunto de Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S} tal que su suma sea igual a Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k} . El algoritmo debe estar basado en programación dinámica. Mostrar que el algoritmo es correcto y demostrar su complejidad.

Ejercicio 2Editar

Decidir si las siguientes afirmaciones son verdaderas o falsas. Justificar.

  • Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} conexo, Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} tiene un único arbol generador si y sólo si Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} es un árbol.
  • Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} tiene un único árbol generador de peso mínimo, entonces Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} es un árbol.
  • Un eje Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle e} de Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} está en todo árbol generador si y sólo si Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle e} es un puente.
  • Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} es un eje que está en un árbol generador mínima si y sólo si Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle e} está en un circuito simple en el cual tiene peso mínimo.

Ejercicio 3Editar

El algoritmo de Dijkstra calcula el camino mínimo entre dos vértices en un grafo con peso en los ejes no negativo. Tenemos un grafo en el cual los vértices también tienen un peso no negativo, el cual se agrega al peso total del camino. Modificar el algoritmo de Dijkstra para poder calcular el camino mínimo en este nuevo grafo. Demostrar que el algoritmo propuesto es correcto.

Ejercicio 4Editar

(a) ¿Puede ser que un grafo Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} y su complemento Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \overline{G}} sean ambos planares? Justificar.

(b) ¿Es cierto que un grafo Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} es planar si y sólo si todos sus subgrafos propios son planares? Justificar.

Ejercicio 5Editar

El problema Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle SubsetSum} decide si dado un conjunto Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S = \{s_1, s_2 \dots s_n\}} y Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k \in \mathbb{N}_0} , existe un subconjunto de Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S} tal que su suma sea igual a Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k} . Este problema es NP-completo. El problema Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle Partition} decide si dado un conjunto Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle S = \{s_1, s_2 \dots s_n\}} , existe una partición en dos subconjuntos tales que la diferencia entre las sumas de los subconjuntos sea menor o igual a Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k} . Demostrar que este problema es NP-completo, utilizando que Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle SubsetSum} es NP-completo.