Edición de «Final del 06/08/18 (Algoritmos III)»

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 <math>d >0 \implies</math> existe un circuito simple de longitud al menos <math>d+1</math> en <math>G</math>.

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

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 <math>G=(V,X)</math> un grafo con una función de peso definida sobre sus aristas, <math> l: X \rightarrow \Re </math>. Probar que <math>\exists e \in X</math> tal que <math>l(e) < l(e'), \forall e' \in X \backslash \{e\}</math> (es decir, hay una arista de peso menor estricto a todas las otras) <math>\implies e</math> pertenece a todo árbol generador mínimo de <math>G</math>.

== Ejercicio 4 ==

Un grafo <math>G</math> es coloreable en forma única si todo coloreo con <math>\chi(G)</math> colores induce la misma partición de los vértices. Probar que si <math>G</math> es coloreable de forma única, entonces el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por los <math>\chi(G)</math> 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 <math>\lambda > 0</math>, el o los cortes mínimos no cambian.
* c) Si se multiplican las capacidades de todos los arcos por <math>\lambda > 0</math>, el valor del o de los cortes mínimos no cambia
* d) Si se suma a las capacidades de todos los arcos <math>\lambda > 0</math>, el o los cortes mínimos no cambia.
* e) Si se suma a las capacidades de todos los arcos <math>\lambda > 0</math>, 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 <math>\Pi_1</math>a uno <math>\Pi_2</math>?
* 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 <math>d</math>, para evitar contraejemplos raros (por ejemplo, en un grafo compuesto por dos <math>K_{2}</math> separados, todos los vértices tienen grado mayor o igual a 1, pero no hay circuitos de longitud 2) que arruinaran la demostración.