Matematica Discreta

FACULTAD DE INGENIERÍA ESC. PROF. DE INGENIERÍA INFORMATICA LABORATORIO 2
Semestre Académico 2011 -II Curso : MATEMÁTICA DISCRETA Grupos : 01 Profesor : Mag. Mas Azahuanche, Guillermo Antonio Fecha: 07 de Octubre del 2011 Instrucciones:  Se permite el uso de copias, apuntes, libros, y los software correspondiente para cada uno de los ejercicios etc.  Proporcione detalles necesarios parajustificar su respuesta  El orden y la limpieza se tomará en cuenta.  Desarrolle con detalle. 1 Estudie cada uno de los grafos y consulte si tiene ciclo o camino hamiltoniano o Euleriano. Es necesarioetiquetar los nodos de (a) y (b)

(c) 2. Sea R una relación en un conjunto finito S con matriz booleana A. Entonces responda adecuadamente cual el concepto que corresponde 1. R es simétrica ⇔ A) A ʘ A A . 2. R es antireflexivo 3. R es reflexiva 4. R es antisimétrica 5. R es total 6. R es asimétrica 7. R es transitiva 3. Del grafo dirigido. Hallar la cerradura transitiva usando el algoritmo deWARSHALL.
5 4 3

⇔ ⇔ ⇔ ⇔ ⇔ ⇔

B) A  A .
T

C) A  A T

no tiene ceros.

D) las entradas en la diagonal de A son todas 1.

E) A  A T  I ; donde I es la matriz identidad.
ó también ⇔diag ( A2 –A ) sólo tiene ceros.

F) diag A2 sólo tiene ceros.
G) las entradas en la diagonal de A son todas 0.
1 2

4. Sean R y S dos relaciones cuyos dígrafos aparecen en las figuras

R
ab

S

a

b

c e d e d c

Calcular:. b) c) d) e) f)

a) El grado interno y grado externo de cada dígrafo

MR , MS ,

R, S
S  , S 1 , S *
2 MS

MR  MS ,
ʘ MS

MR  MS

g) M R5. Dar la tabla de funcionamiento para la expresión booleana Z=
 

Hacer el mapa de Karnaugh. ¿Es ésta la mínima expresión booleana que produce la salida Z? De no serlo, indicar cuál sí loes. Dibujar el circuito con menor número de compuertas que produce la salida Z.



6. Determinar si los siguientes pares de grafos son isomorfos:

7.- Dé la matriz de adyacencia de: A) B)...