Edición de «Final del 06/08/18 (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
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. |