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

Nombre: ______________________________________________ Código: ______________________ 1. (10) Dados los grafos Km,n y Cn :

¿Para cuales valores de n, los grafos tienen un camino de Euler pero no un circuito de Euler?

2. (10) Construya un árbol ordenado etiquetado cuyo recorrido preorden es a, b, f, c, g, h, i, d, e, j, k, l, m; donde a tiene 4 hijos; c y j tienen 3 hijos; b y e tienen un hijo, y todos los otros vértices son hojas.

3. (10) Escriba el recorrido postorden del árbol generado en el punto anterior.

4. (20) Supongamos que m es un entero con m≥2. Un código de Huffman m-ario para un conjunto de N símbolos se puede construir de manara análoga a la construcción del código de Huffman binario. En el paso inicial, se combinan ((N - 1) mod (m - 1)) + 1 árboles de peso mínimo que constan de un solo vértice para formar un árbol con raíz que tiene a estos vértices como hojas. En cada uno de los pasos siguientes, los m árboles de menor peso se combinan para formar un árbol m-ario. Use codificación 3-aria de Huffman para TECNICO EN SISTEMAS DE INFORMACION GEOGRAFICA

5. (10) Encontrar una solución al problema de las 6-Reinas

6. Responda las preguntas a partir del siguiente grafo:

a. (10) Use Kruskal para hallar el camino y el peso del árbol de expansión mínimo.

b. (10) Hallar el camino más corto entre a e i, muestre cada uno de los pasos.

c. (10) Use el algoritmo de Búsqueda en Profundidad para obtener el árbol generador a partir del vértice a.

d. (10) Hallar el número cromático del grafo. Muestre los pasos para hallarlo.

Éxito!

a b c

d f

g h i

5 4

32

6

4 2

4

36

1

3

5

7

48

e