1

ASIGNATURA : INTRODUCCION A LA MATEMATICA DISCRETA PROFESORES : Erik Papa - Ricardo Chung Simn Mndez AULA : TODAS LAS AULAS - Turno Maana FECHA : lunes 07 de agosto del 2012 11:20 12:40 Horas. TEMA : Teora de Grafos Arboles Mquinas de Estado Finito

Duracin 80 minutos PROHIBIDO el uso de cuadernos, apuntes, formularios, libros, fotocopias, celulares, MP3, MP4, Discman y dems objetos sospechosos. PROHIBIDO prestarse calculadoras. Cada pregunta vale 4 Puntos

Examen Final UNICO

1. En el grafo de la figura se han

representado las seis paradas de una ruta escolar y las distintas conexiones entre las mismas.

A) Hallar la Matriz de adyacencia del Grafo.

B) Razonar si es posible recorrer todas las calles una sola vez, aunque se pase por ms de una vez por alguna parada. En caso afirmativo encuntrese un recorrido con esas caractersticas, partiendo de B.

2. La tabla siguiente muestra informacin (las primeras componentes) acerca

de las distancias (en millas) entre pares de ciudades en el estado

norteamericano de Indiana y las segundas componentes de los pares

ordenados indican el costo por milla de construccin. La empresa

Carreteras SAC construir una red de carreteras para unir estas seis

ciudades.

A) Determine las carreteras que deben construirse a fin de minimizar el

costo de la construccin, asumiendo que el costo de una milla de

construccin es igual entre cada pares de ciudades.

Facultad de Ingeniera Industrial y de Sistemas e Industrial

2

B) Si consideramos que el costo por milla de carretera construida vara

segn la segunda componente de los pares ordenados, en miles de

dlares, resolver la misma pregunta.

C) Si se agrega la restriccin que la construccin debe incluir una carretera

entre Gary y Evansville encuentre el nmero de millas que debe

construirse tanto en el caso A como en el caso B.

3. Un documento contiene 100,000 caracteres distribuidos en la forma

siguiente: A: 18000, E: 11000, D: 13000, L: 16000, M: 2000, U: 5000, R: 9000, N: 7000, J: 1000, O: 15000 y G: 3000. a) Hallar una Codificacin utilizando igual nmero de bits para cada

carcter. b) Hallar una codificacin utilizando distintos nmeros de bits para los

caracteres. c) Hallar la codificacin segn Huffman, utilizando el Algoritmo de

Huffman. Considere que si la fusin tiene un valor igual al de una letra, dicha suma precede a la letra.

En todos los casos halle tambin la longitud total del documento comprimido, considerando longitud total mnima. d) Eligiendo SIEMPRE, la rama de la izquierda CERO y la rama de la

derecha UNO decodificar el mensaje que se recibi: 011111_111011110001011010000010100011_100011111_000101011011101. Considere que los guiones son solamente separadores no codificados.

4. En la grfica mostrada, hallar:

A) Un rbol recubridor de peso mnimo

con el algoritmo de Kruskal.

B) La ruta ms corta para ir desde E

hacia los dems vrtices usando el

algoritmo de Dijkstra. Muestre adems

las tabulaciones a realizar para la

eleccin de los vrtices.

5. La siguiente expresin es la notacin polaca de una operacin:

+ x + - 2 1 6 7 + - 8 9 10.

A) Hallar la operacin inicial, que dio origen a dicha notacin polaca.

B) Hallar la digrfica del rbol.

C) Hallar la notacin polaca inversa.