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