UNIVERSIDADE DOS AÇORES
Departamento de Matemática
Escola Superior de Tecnologia e Administração
Tópicos de Matemática Discreta - Informática-Redes e Multimédia
Teste 1 - 5/12/2006
Parte I
1. Considere as seguintes relações de ordem parcial:
(a) AρB se e só se A ⊆ B com A e B elementos de
P = {{a}, {b}, {c}, {a, b}, {a, c}, {a, b, c}}.
(b) R = {(a, a), (b, b), (c, c), (d, d), (a, d), (d, b), (a, b), (a, c)} em
S = {a, b, c, d}.
Complete os seguintes quadros:
Diagramas de Hasse
(a) Relação ρ
(b) Relação R
Elementos Extremais
(a) Relação ρ
(b) Relação R
maximais
minimais
máximo
mínimo
V.S.F.F.
1
2. Considere o grafo dirigido G = (V, A) onde V = {x, y, z, w} e
A = {(y, x), (x, z), (x, w), (z, w), (w, y)}
Complete os seguintes quadros:
Representação gráfica de G = (V, A)
Grau externo de x
Grau interno de y
Grau total de W
Um caminho elementar de comprimento 2
de x para y
Distância de x a y
Ciclo elementar com vértice inicial em w
A = {P |P caminho elementar de x para w}
A={
NOME:————————————————————————-
2
UNIVERSIDADE DOS AÇORES
Departamento de Matemática
Escola Superior de Tecnologia e Administração
Tópicos de Matemática Discreta - Informática-Redes e Multimédia
Teste 2 - 5/12/2006
Parte II
1. Considere a sucessão definida recursivamente por
• a1 = 1
• an+1 = an + 8n, n ≥ 1
(a) Determine os primeiros quatro termos da sucessão.
(b) Mostre, por indução matemática, que
an = (2n − 1)2 , ∀n ∈ N
2. (a) Determine uma fórmula para
1 + 3 + 5 + 7 + ... + (2n − 1) com n ≥ 1,
analisando os valores da expressão para os primeiros valores de n.
(b) Use Indução matemática para provar que a conclusão a que chegou
está correcta.
Se não resolveu a alínea (a), prove por Indução Matemática que
2 + 4 + 6 + 8 + ... + (2n) = n(n + 1) para todo o n ≥ 1
(c) Use o resultado anterior para calcular a soma de todos os números
impares positivos menores do que 122.
Se não resolveu a alínea (a), use o resultado anterior para calcular a soma de todos os números pares positivos menores do que
123.
V.S.F.F.
3
3. Seja B = {0, 1, 21 }. Para cada árvore binária não vazia T , r(T ) designa a raiz
de T . Vamos chamar admissíveis a todas aquelas árvores binárias sobre B
definidas recursivamente por:
1. Se a ∈ B então < a > é uma árvore admissível.
2. Se a ∈ B e U e V são árvores admissíveis tais que
r(U ) + r(V ) = 1 então a árvore < a; U, V > é admissível.
(a) Represente graficamente as seguintes árvores binárias sobre o conjunto B
T1 =<
1
1
; < 0; < 1 >, < 0 >>, < 1; < 1; < >, < 1 >>, < 0 >>>>
2
2
T2 =< 0; < 1 >, < 0; <
1
1
>, < >>>
2
2
(b) As árvores T1 e T2 dadas são admissíveis? Justifique.
(c) Apresente:
(i) Todas as árvores admissíveis de altura 2.
(ii) Duas arvores admissíveis de altura 3.
(iii) Duas árvores binárias sobre o conjunto B de altura 3 que não sejam
admissíveis.
Cotação:
Parte I
1. 4.0
2.
3.5
Parte II
1. 2.5
2.
5.0
3.
5.0
4