Un Examen Parcial III - Matemática Discreta

Universidad de Costa Rica

Escuela de Ciencias de la Computación e Informática

CI-1204 Estructuras Discretas

Prof. M.Sc. Kryscia Daviana Ramírez Benavides

I Semestre 2012                                                                                        Fecha: 30/06/2012

Examen Parcial III

Indicaciones Generales

• Hacer el desarrollo de cada ejercicio completo, ordenado y legible.
• Realizar todos los pasos en cada ejercicio.

1. (20pts) Resuelva las siguientes relaciones de recurrencia homogéneas. Indique en cada una la ecuación característica, las raíces características y la solución general.

1. (5pts) 5an+1 = -10an, n ≥ 0, a2 = 20.
2. (5pts) an+1 = 7an, n ≥ 0, a5 = 50421.
3. (5pts) an+2 = 6an+1 – 9an, n ≥ 0, a0 = 1, a1 = 2.
4. (5pts) an+2 + 3an+1 + 2an = 0, n ≥ 0, a0 = 0, a1 = 1.

1. (20pts) Resuelva las siguientes relaciones de recurrencia no homogéneas. Indique en cada una la ecuación característica, las raíces características, el f(n), la solución homogénea asociada, la solución particular y la solución general.

1. (10pts) an+1 = 7an + 1, n ≥ 0, a0 = 3.
2. (10pts) an+2 – 6an+1 + 9an = n + 5, n ≥ 0, a0 = 1, a1 = 2.

1. (10pts) Resuelva la siguiente relación de recurrencia no lineal y no homogénea. Indique la ecuación característica, las raíces características, la solución homogénea asociada, la solución particular y la solución general.

1. (10pts) an+22 – 5an+12 + 4an2 = 2n, n ≥ 0, a0 = 1, a1 = 4.

1. (30pts) Con el grafo dirigido de la figura 1 realice los siguientes ejercicios.

1. (20pts) Utilice el algoritmo de Floyd para encontrar las distancias más cortas entre todos los pares de vértices del grafo y, construya la matriz P que permite recuperar los caminos más cortos. Dibuje el grafo para los caminos más cortos para el vértice d.
2. (5pts) Del ejercicio anterior obtenga la cerradura transitiva y la excentricidad del grafo, indique ¿cuál es el centro del grafo?
3. (5pts) Realice el recorrido de búsqueda en profundidad empezando en el vértice a y siguiendo el orden alfabético. Recuerde señalar e indicar los diferentes arcos para construir el bosque abarcador en profundidad.

1. (25pts) Con el grafo no dirigido de la figura 2 realice los siguientes ejercicios.

1. (10pts) Aplique el algoritmo del camino más corto para llegar del vértice a al vértice h. Dibuje como quedó el grafo al final.
2. (5pts) Utilice el algoritmo de Kruskal para hallar el árbol abarcador de costo mínimo del grafo empezando en el vértice a y siguiendo el orden alfabético.
3. (5pts) Realice el recorrido de búsqueda en amplitud (anchura) empezando en el vértice a y siguiendo el orden alfabético. Recuerde señalar e indicar las diferentes aristas para construir el bosque abarcador en amplitud (anchura).
4. (3pts) ¿Cuántos caminos simples diferentes existen entre a y h? Enumérelos.
5. (2pts) ¿Cuántos ciclos simples diferentes existen para a?

EXTRA. Para que estas preguntas sean tomadas en cuenta en la nota final del examen, debe haber contestado las preguntas anteriores en su totalidad. Utiliza tu pensamiento lateral y razonamiento para resolver el siguiente problema.

...