Examen Matemáticas Discretas – Corte II Universidad del Pacífico Docente: Esteban Andrés Díaz Mina 13 de mayo de 2016

Nombre Completo: ______________________________________________________

Justifique la respuesta de cada una de las siguientes preguntas: 1. (10) Dado el grafo Km,n:

¿Para cuales valores de n y m, este grafo tiene un camino de Euler?

2. (10) Un grafo simple es llamado regular si cada vértice de este grafo tiene el mismo grado. Un grafo es llamado n-regular si cada vértice en el grafo es de grado n.

¿Para qué valores de n el grafo Wn no es regular?

3. (1.0) ¿Existe un grafo simple de seis vértices con la lista de grados 3, 3, 4, 4, 4, 6? Si

existe dibújelo, si no existe justifique su respuesta.

4. (50) Como es de conocimiento general, en los pueblos se toma como referencia de

ubicación los sitios públicos. En el pueblo NuevaAventura donde vive el señor

Jóse_Santos, se tienen los siguientes sitios públicos: Alcaldía, Parque,

Supermercado, Estadio, Prendería, Guardería, Panadería y un enlace que

representa el hecho de que se puede desplazar de un sitio a otro.

{Alcaldía, Parque}=6 {Parque, Estadio}=1

{Prendería, Supermercado}=3 {Supermercado, Parque}=10

{Alcaldía, Panadería}=3 {Panadería, Estadio} =3

{Prendería, Parque}=6 {Prendería, Panadería}=2

{Panadería, Guardería}= 7 {Prendería, Guardería}=3

Dibuje el grafo G, que represente la ubicación de los sitios del Pueblo. a. (20) Use el algoritmo de Dijkstra para hallar el camino más corto entre el

Prendería y Estadio. Muestre la secuencia de vértices visitados. b. (10) Determine si el grafo G tiene un camino de Euler. Si existe muestre el

camino.

c. (10) ¿Cuántos caminos distintos de longitud 4 existen entre la Alcaldía y el Parque? Muéstrelos.

d. (10) Use el algoritmo de Búsqueda en Anchura para obtener el árbol generador a partir del vértice Alcaldía. Use orden alfabético para visitar los vértices del grafo.

5. (10) El departamento de Sistemas tiene seis comisiones que se reúnen una vez

al mes. ¿Cuántos espacios de reunión distintos se necesitan para asegurar que a ningún miembro del departamento se le convoca para asistir a dos reuniones al mismo tiempo si las comisiones son C1={Arias, Zuluaga}, C2={Barco, Lozano}, C3={Arias, Ruiz, Zuluaga}, C4={Lozano, Ruiz, Zuluaga}, C5={Arias, Barco} y C6={Barco, Ruiz}?

6. (10) Crear un árbol binario de búsqueda a partir de los siguientes números:

14 12 5 54 46 8 43 7 9 3

¿Cuántas comparaciones son necesarias para encontrar el número 43?

Éxitos!