Diferencia entre revisiones de «Final del 06/08/18 (Algoritmos III)»
(Página creada con «Final escrito de Paula Zabala. = Enunciados = == Ejercicio 1 == Sea <math>G=(V,X)</math> un grafo. Probar que si <math>d(v) \geq d, \forall v \in V </math> para algún <m...») |
mSin resumen de edición |
||
(No se muestra una edición intermedia del mismo usuario) | |||
Línea 4: | Línea 4: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
Sea <math>G=(V,X)</math> un grafo. Probar que si <math>d(v) \geq d, \forall v \in V </math> para algún <math>d >0 \implies</math> existe un circuito simple de longitud al menos <math>d+1</math> en <math>G</math>. | Sea <math>G=(V,X)</math> un grafo. Probar que si <math>d(v) \geq d, \forall v \in V </math> para algún <math>d > 0 \implies</math> existe un circuito simple de longitud al menos <math>d+1</math> en <math>G</math>. | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Dados <math>G=(V,X)</math> un digrafo con pesos en sus aristas, <math>s \in V</math> y <math>k</math> un entero positivo, se quiere hallar los <math>k</math> vértices más cercanos a <math>s</math> con un algoritmo cuya complejidad sea <math>O(nk)</math>. | Dados <math> G=(V,X)</math> un digrafo con pesos en sus aristas, <math>s \in V</math> y <math>k</math> un entero positivo, se quiere hallar los <math>k</math> vértices más cercanos a <math>s</math> con un algoritmo cuya complejidad sea <math>O(nk)</math>. | ||
a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no. | a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no. |
Revisión actual - 16:16 24 oct 2018
Final escrito de Paula Zabala.
Enunciados
Ejercicio 1
Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G=(V,X)} un grafo. Probar que si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d(v) \geq d, \forall v \in V } para algún Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d > 0 \implies} existe un circuito simple de longitud al menos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d+1} en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} .
Ejercicio 2
Dados Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G=(V,X)} un digrafo con pesos en sus aristas, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle s \in V} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k} un entero positivo, se quiere hallar los Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k} vértices más cercanos a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle s} con un algoritmo cuya complejidad sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle O(nk)} .
a) ¿Se puede modificar fácilmente el algoritmo de Dijkstra para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no.
b) ¿Se puede modificar fácilmente el algoritmo de Bellman-Ford para resolver esto? En caso afirmativo, explicar cómo; en caso negativo, justificar por qué no.
Ejercicio 3
Dado Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G=(V,X)} un grafo con una función de peso definida sobre sus aristas, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle l: X \rightarrow \Re } . Probar que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists e \in X} tal que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle l(e) < l(e'), \forall e' \in X \backslash \{e\}} (es decir, hay una arista de peso menor estricto a todas las otras) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \implies e} pertenece a todo árbol generador mínimo de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} .
Ejercicio 4
Un grafo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} es coloreable en forma única si todo coloreo con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi(G)} colores induce la misma partición de los vértices. Probar que si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle G} es coloreable de forma única, entonces el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por los Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi(G)} colores es un subgrafo conexo.
Ejercicio 5
Decidir si las siguientes afirmaciones son verdaderas o falsas. Justificar.
- a) Si todos los arcos de una red tienen diferentes capacidades, la red tiene un único corte mínimo.
- b) Si se multiplican las capacidades de todos los arcos por Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda > 0} , el o los cortes mínimos no cambian.
- c) Si se multiplican las capacidades de todos los arcos por Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda > 0} , el valor del o de los cortes mínimos no cambia
- d) Si se suma a las capacidades de todos los arcos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda > 0} , el o los cortes mínimos no cambia.
- e) Si se suma a las capacidades de todos los arcos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \lambda > 0} , el valor del o de los cortes mínimo no cambia.
Ejercicio 6
- a) ¿Cuándo un problema pertenece a la clase P?
- b) ¿Cuándo un problema pertenece a la clase NP?
- c) ¿Cuándo un problema pertenece a la clase NP-C?
- d) ¿Qué es una reducción polinomial de un problema de decisión Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_1} a uno Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Pi_2} ?
- e) Demostrar que el problema de conjunto independiente máximo (en su versión de decisión) pertenece a la clase NP.
- f) En la práctica, ¿cómo se demuestra que un problema pertenece a la clase NP-C? Justificar.
- g) Enunciar 5 problemas estudiados en la materia que sean P y 5 que sean NP-C.
Notas
En el ejercicio 1, aclaró en el momento del examen que supongamos una cota 'conveniente' para Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d} , para evitar contraejemplos raros (por ejemplo, en un grafo compuesto por dos Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{2}} separados, todos los vértices tienen grado mayor o igual a 1, pero no hay circuitos de longitud 2) que arruinaran la demostración.