TP_MD_2 CUATRIMESTRE 2019

Vista previa del material en texto

Página 29 de 48 
 
 
2019 
 
MATEMÁTICA DISCRETA 
Trabajos Prácticos 
2°cuatrimestre 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 31 
 
 
MATEMATICA DISCRETA 
 TRABAJO PRACTICO Nº4 
SUCESIONES, INDUCCIÓN Y RECURSIVIDAD 
1) i) Sea el alfabeto A = {a, b, c ,d }, escribir por extensión los siguientes subconjuntos 
de * 
a) { x / x es una palabra de longitud 2 donde no se repitan los símbolos} 
b) {x / x es una palabra de longitud 3 que comienza con c} 
c) {x / x es una palabra de longitud 3 de símbolos distintos y que comienza con c} 
 
ii) Sugerir un alfabeto de 3 símbolos y escribir el conjunto de palabras generadas por 
él hasta las de longitud 3 
 
2) Encontrar la fórmula explícita de las siguientes sucesiones: 
a) 
 
 
 
 
 
 
 
 
 
b) 3, 9, 27, 81,…. 
c) -5 , 9 , -13 , 17 , -21 , .... 
d) -2, 4, -6, 8,…. 
e) ,....
8
1
,
4
1
,
2
1
,1  
f) -4,-2, 0, 2, 4, 6, 8,… 
 
3) Se sabe que la suma de términos de una progresión aritmética está dada por 
 
 
 
 
 
, donde es el primer término y es la diferencia 
entre dos términos consecutivos, 
Aplicando estas fórmulas calcular el resultado de las siguientes sumas: 
a) (100 términos) 
b) 
c) 
 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 32 
 
4) Se sabe que la suma de términos de una progresión geométrica está dada por 
 
 
 
 
 
, donde es el primer término y es el cociente dos 
términos consecutivos, 
 
 
 . 
Aplicando estas fórmulas calcular el resultado de las siguientes sumas: 
a) 
b) 
 
 
 
 
 
 
c) 
 
5) Indicar cuantos términos tienen las siguientes sumas y desarrollarlas. Encontrar el 
valor de las sumas y describir en palabras a la expresión resultante: 
a) c) 
 
 
b) 
d) 
6) Abreviar usando el símbolo  las siguientes sumas 
a) 
 
 
 
 
 
 
 
 
 
 
 
 
b) 
c) 
 
 
 
7) Interpretar y demostrar las siguientes igualdades 
i) 
 
ii) 
iii) 
 
 
 
iv) 
 
v) 
 
8) Encontrar la fórmula de recurrencia para la siguientes sucesiones 
a) 1 ,3 , 12 , 60 , 360 , ... 
b) 3 , 3 , 6 , 9 , 15 , 24 , ... 
c) 0 , 2 , 6 , 14 , 30 , 62 , ... 
d) 
 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 33 
 
e) 
f) 
 
9) Clasificar a las siguientes relaciones de recurrencia: 
a) 
b) 
 
c) 
d) 
e) 
 
10) Clasificar y encontrar la solución general de siguientes relaciones de recurrencia : 
a) 
b) 
c) 
d) 
e) 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 35 
 
MATEMATICA DISCRETA 
 TRABAJO PRACTICO Nº5 
GRAFOS, DIGRAFOS Y ARBOLES 
 
1) Sea el grafo G=(V, A, ), donde V={ 1 , 2 , 3 , 4 } , A = { } y  dada 
por 
 
 
i) ¿Es un grafo simple? ¿Es completo? ¿Es regular? Justifique sus respuestas 
ii) Calcular el grado de cada vértice y comprobar la propiedad. 
iii) Confeccionar las matrices de adyacencia y de incidencia. ¿Cuál de las dos es 
suficiente para representar al grafo? 
2) Trazar el grafo G = ( V, A,  ), donde V={ a , b , c , d , e , f , g , h } , A={ a1, a2, a3, ……. , a9}, 
donde la función  esta dada por: 
 
 
 
 
a) ¿Es G un grafo simple?.¿Es regular? ¿Es completo ? . ¿Es bipartito? ¿Es bipartito 
completo?. Justificar su respuesta 
b) Confeccionar su matriz de adyacencia y de incidencia. Analizar el resultado de sumar 
los valores de cada fila y cada columna de ambas matrices. 
c) Encontrar, si existe: 
i) algún camino elemental pero no simple a – e 
ii) algún camino simple a – e de longitud mayor que 1 y 
iii) un circuito e – e que no sea ciclo 
iv) un ciclo e – e 
 
 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 36 
 
3) Dado el siguiente grafo, donde V={1,2,3,4,5,6,7,8,9} 
a) Encontrar los siguientes subconjuntos de V: 
Vi = { v  V / g(v) = i } para i = 1,2,3…5 
b) Colorear de distinto color a cada Vi 
c) Mostrar que { V1 ,V3 ,V4 ,V5 } es una partición de V 
4) Dado el grafo G = ( V, A,  ), donde V={ a , b , c , d , e , f , g , h } 
 
 
a) Colorear los vértices de tal modo de usar 
la cantidad de colores minimo y de tal 
modo que no haya dos adyacentes del 
mismo color. 
b) Responda: Es un grafo bipartito? 
Justifique la respuesta 
 
 
5) a) Dibujar K1 , K2 , K3 , K4 , K5 y K6 
b) Escribir la sucesión de la cantidad de aristas de los grafos completos Kn, en forma explícita 
y recursiva. 
6) En cada apartado, trazar un grafo que cumpla con las condiciones indicadas. En caso de no 
existir, justificar. 
a) Que posea 10 vértices y cuyos grados sean: 1, 2, 5, 3, 1, 2, 3, 3, 2, 4 
b) Que posea 12 vértices tal que dos de sus vértices sean de grado 4 , tres de grado 1 y 
cuatro de grado 2 y tres vértices aislados 
c) Que sea regular con 5 vértices y 10 aristas 
d) Que sea regular con 4 vértices y 6 aristas pero distinto de K4 
e) Que sea completo con 45 aristas. 
f) Que sea completo con 300 aristas. 
g) Que sea bipartito completo con 8 vértices y 15 aristas. 
h) Que sea bipartito completo con 11 vértices y 21 aristas. 
i) Que sea bipartito no completo con 6 vértices 
 
 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 37 
 
7) a) Un grafo posee 7 vértices y 12 aristas y es tal que tiene un vértice de grado 3, dos de 
grado 5 y tres de grado 2. ¿Cual es el grado del 7° vértice? 
b) ¿Cuántas aristas posee un grafo 3 – regular con 10 vértices? 
c) Un grafo bipartito completo tiene 9 vértices de grado 4, ¿Cuántos vértices de grado 9 
posee? ¿Cuántos vértices en total? 
d) ¿Cuántas aristas posee un grafo completo de 25 vértices? 
e) ¿Cuántas vértices posee un grafo completo de 153 aristas? 
f) Cuantas aristas posee un grafo G donde V = { v1, v2, v3, v4, v5 ,v6 , v7 , v8 } donde se 
cumple que la función grado está definida por g(vi) = i+1 , i = 1 , ..., 8 
 
8) Sea el siguiente grafo 
 
 
Hasta la 5° fila de la siguiente tabla marca con una tilde la clasificación que corresponda para 
cada sucesión de vértices que se da e indica la longitud. Luego de la 5° fila completa en la 
primera columna con una sucesión de vértices o aristas que cumplan las especificaciones 
dadas con ejemplos distintos a los dados 
 Trayectoria 
(o Camino) 
 Camino 
simple 
Camino 
elemental 
Circuito Ciclo Long. 
2,3,4,2 
a1,a3,a8 ,a2 
6,1,2,4,1,7,6 
a3,a7,a5,a2,a1 
2,3,4,2,1,4,2 
    
      
  
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 38 
 
9) Para el grafo del ejercicio 8, calcular la matriz de adyacencia y verificar la propiedad que 
ella satisface calculandoel cuadrado y el cubo de la misma 
10) Determinar si H1 , H2 y H3 son subgrafos de K6 
 
 
 
11) Dado el siguiente grafo 
 
Obtener los siguientes subgrafos, analítica y gráficamente 
i) 
ii) 
iii) 
 donde 
iv) 
 donde 
v) 
 donde 
vi) 
 donde 
 
12) Observar cada grafo de este ejercicio e indicar si posee aristas puentes o vértices istmos. 
También encontrar, si existen Ciclos de Euler o de Hamilton, Caminos de Euler o de Hamilton 
o ninguno de éstos. En caso afirmativo brindar la sucesión respectiva, en caso negativo, 
justificar su respuesta. 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 39 
 
 
 
13) En cada apartado indicar si los grafos que se dan son isomorfos. Justificar cualquiera sea 
la respuesta 
 
 
 
 
 
 
 
 
 
 
 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 40 
 
 
14) Dados los siguientes grafos, determinar cuál de ellos es árbol 
 
En los casos afirmativos, verifique las propiedades de los arboles 
15) Diga verdadero o Falso justificando la respuesta: 
a) Existe un árbol de 21 vértices y 19 aristas 
b) Si un grafo posee 21 vértices y 20 aristas entonces es un árbol 
c) Si un grafo con n vértices es un árbol entonces posee n – 1 aristas 
d) En un árbol no existen istmos. 
e) En un árbol no existen puentes. 
f) En un árbol no existen vértices de grado 1 
g) Todo grafo conexo es un árbol. 
h) Todo árbol es un grafo conexo 
i) Si un grafo tiene lazos no es árbol. 
j) Si un grafo tiene aristas paralelas no es árbol 
16) Sea el digrafo G= (V, A , ) donde V = { a , b , c , d , e , f }, A = {e1, e2, e3, e4, e5, e6 , e7 } y 
 dada por 
 
 
 
 
 
Representar gráficamente y responder: 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 41 
 
i) ¿Posee bucles, vértices aislados, vértices y aristas adyacentes? ¿Existen aristas 
paralelas o antiparalelas? ¿Qué tipo de grafo es? 
ii) Obtener las matrices de Adyacencia e Incidencia de G 
iii) Obtener al menos dos caminos y dos ciclos, indicar sus longitudes 
iv) Indicar si hay vértices fuentes y vértices pozos 
17) Definir a los dígrafo G=(V, E, ) dados por 
 
En cada caso 
i) Indicar lazos, aristas paralelas y antiparalelas, si es que existen. 
ii) Dar dos ejemplos de aristas adyacentes para cada uno 
iii) Indicar el camino simple de mayor longitud existente en cada digrafo. Indicar el 
ciclo simple, si existe, de mayor longitud existente en cada digrafo 
iv) Para cada uno de los dígrafos hallar la matriz de adyacencia y, si es pertinente, la 
matriz de incidencia. 
 
18) Con referencia al siguiente dígrafo: 
Encontrar: 
a) El camino simple de mayor longitud entre v6 y v3 
b) El camino elemental de mayor longitud entre v2 y v7 
c) Un circuito de Euler y un ciclo de Hamilton, si existen. 
 
 
 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 42 
 
 
19) Definir al Digrafo simple representado por la matriz de adyacencia M 
a) Hallar pozos y fuentes 
b) Hallar el grado positivo y el grado 
negativo, el grado total y el grado neto para 
cada uno de los vértices. 
c) Verificar las propiedades de los grados 
c) Determinar si el digrafo posee circuito de 
Euler y ciclo de Hamilton 
 
20) Dada la siguiente matriz de incidencia de un Digrafo G, trazarlo y responder: 
 
i) ¿Posee pozos y fuentes? 
ii) ¿Posee circuito de Euler? 
iii) ¿Posee ciclo de Hamilton?. 
En caso afirmativo, escriba las 
secuencias correspondientes 
 
 
21) Trazar los grafos asociados a los siguientes dígrafos 
 
a) b) 
 
 
 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 43 
 
22) Sean los siguientes dígrafos. Determine cuál de ellos representa a un árbol y cuál de 
ellos representa un árbol dirigido con raíz, indicando a la misma. 
a) b) 
 
 
c) d) 
 
23) Dado un árbol binario regular (o completo), contestar: 
a) ¿ Cual es la relación existente entre la cantidad de vértices internos y vértices hojas? 
b) Si el árbol es pleno, ¿cual es la relación entre la cantidad de vértices hojas y la altura 
del árbol? 
c) ¿Existe un árbol binario regular con 10 vértices internos y 11 vértices hojas? 
d) ¿Existe un árbol binario regular y pleno (o total) con 100 hojas? 
 e) ¿Existe un árbol binario regular con todos los vértices con grado de entrada 1? 
 
24) Encontrar los recorridos de los siguientes arboles 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 44 
 
 
25) Construir el árbol correspondiente a las expresiones algebraicas siguientes y obtener las 
expresiones prefija, posfija e infija de las expresiones 
 a) b) 
26) Identificar las notaciones que se dan a continuación, construir el árbol que corresponde 
en cada caso y encontrar las otras dos notaciones que los representan 
i) 
ii) 
iii) 
iv) 
 
27) Sabiendo que y , calcular el valor de 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 45 
 
MATEMATICA DISCRETA 
 TRABAJO PRACTICO Nº6 
ESTRUCTURAS ALGEBRAICAS FINITAS 
 
1) Sea el conjunto Z y * la ley de composición interna definida por a * b= a + b - 1. 
Demostrar que * es asociativa, conmutativa, posee elemento neutro y que cada 
elemento tiene inverso. Z posee elementos idempotentes respecto de *? 
 
2) Sea A= {0,1} 
a) Realiza la tabla para cada una de las 16 operaciones binarias cerradas que 
pueden definirse sobre A 
b) ¿Cuáles de las operaciones definidas en a) son conmutativas? 
c) ¿Cuáles tienen elemento neutro? 
d) Identifica entre las leyes dadas en a) aquellas que posean elementos 
 idempotentes. 
e) ¿En cuál operación cada elemento tiene inverso? 
 
3) La siguiente tabla define a la operación + en el conjunto A = {s, t, x, y} 
 
 
 
 
 
a) ¿Es conmutativa? 
b) ¿Tiene elemento neutro? ¿Cuáles son los elementos que admiten inverso en A? 
 
4) Sea A= {a, b}. ¿Cuáles de las leyes de composición interna definidas en A, dadas por 
las tablas siguientes definen un semigrupo con elemento neutro? 
 
 
 
 
+ s t x y 
s y x s t 
t x y t s 
x s t x y 
y t s y x 
a) * a b b) * a b 
 a a b a a b 
 b b a b a a 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 46 
 
5) Sea el conjunto R – { 0 } y sea * la operación definida por a * b =( a.b) /2. 
Mostrar que (R – { 0 } , *) es un grupo abeliano. 
 
6) Sea A= { x, y, z, t }.Demostrar que (A, *) y (A , #) son grupos 
a) * x y z t b) # x y z t 
 
x x y z t 
 
x x y z t 
 
y y x t z 
 
y y x t z 
 
z z t x y 
 
z z t y x 
 
t t z y x 
 
t t z x y 
 
7) Completar la siguiente tabla buscando que el conjunto A = { 1 , 2 , 3 , 4 } sea grupo 
respecto de la operación * , de tal modo que 3 sea el elemento neutro y que 2’= 4 
 
 
 
 
 
 
8) Completar la siguiente tabla buscando que el conjunto A= { 1 , 2 , 3 , 4 } sea grupo 
respecto de la operación * , de tal modo que 2 sea el neutro y que las ecuaciones 1 * x = 4 y 
x * 4 = 2 se satisfagan para x = 3 
 
 
 
 
 
 
9) Sea X = { a , b } y sea A = P(X) = {  , {a} , {b} , {a ,b} } . 
Responder, justificando su respuesta: ¿Tiene ( A ,  ,  ) estructura de Anillo , donde  es 
la operación Diferencia Simétrica y  la operación Intersección entre conjuntos? 
 
* 1 2 3 4 
1 
 2 
 3 
 4 
 
* 1 2 3 4 
1 
 2 
 3 
 4 
 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 47 
 
10) Sea A= { a , b , c} un conjunto donde se definen las operaciones + y * por medio de 
las siguientes tablas 
 
 
 
 
Responder, justificando su respuesta:¿Es (A, +,*) un anillo? 
 
11) Sea A= {0,1, 2, 3} un conjunto donde se definen las operaciones + y * por medio de 
las siguientes tablas 
 
 
 
 
Responder, justificando su respuesta: ¿Es (A, +,*) un anillo? ¿Es A un anillo conmutativo con 
unidad? 
 
12) Sea el conjunto C = { 0 , 1 } y las operaciones + y . dadas por las tablas 
 
Mostrar que ( C . + , . ) tiene estructura de cuerpo 
 
13) Sea C = { 0 , 1 , 2 } y las operaciones + y * dadas por las tablas 
 
1+1 0 1 2 
 
1*1 0 1 2 
0 0 1 2 
 
0 0 0 0 
1 1 2 0 
 
1 0 1 2 
2 2 0 1 
 
2 0 2 1 
 
Responder, justificando su respuesta: ¿Tiene ( C . + , * ) estructura de cuerpo? 
 
+ a b c 
a c a b 
b a b c 
c b c a 
* a b c 
a a b c 
b c a b 
c b c a 
+ 0 1 2 3 
0 0 1 2 3 
1 1 2 3 0 
2 2 3 0 1 
3 3 0 1 2 
* 0 1 2 3 
0 0 0 0 0 
1 0 2 0 2 
2 0 0 0 0 
3 0 2 0 2 
 
UTN – FRT – MATEMATICA DISCRETA 2018 pág. 48 
 
14) Señalar cuales de las siguientes ternas representan una estructura de Cuerpo. 
En todos los casos se trata de un conjunto particular Zn, donde las operaciones son entre 
clases de congruencia y están definidas de la siguiente manera: 
[a]n+[b]n=[a+b]n 
[a]n.[b]n=[a.b]n 
i) ( Z5 , + , . ) donde Z5 es el conjunto de las clases de congruencia módulo 5 
ii) ( Z4, + , . ) donde Z4 es el conjunto de las clases de congruencia módulo 4 
 
15) Sea B = { 0 , 1 } y las operaciones + y * dadas por 
 0 1 
 
 0 1 
0 0 1 
 
0 0 0 
1 1 1 
 
1 0 1 
 
Demostrar que ( B , + , * ) tiene estructura de Algebra de Boole 
 
16) Sea P(X) el conjunto Potencia de X, donde X = { a , b } y sean las operaciones unión 
e intersección . Demostrar que (P(X),  , ) constituye un álgebra booleana. 
 
17) Sea Dn el conjunto de los divisores positivos de n y sean las operaciones 
x + y= mcm(x, y) , x * y= mcd(x, y) 
Realizar las tablas de las operaciones para los siguientes valores de n y determine si es 
álgebra de Boole en cada caso 
i) n=7 
ii) n=10 
iii) n=15