ESCOLA SUPERIOR DE TECNOLOGIA DE SETÚBAL
DEPARTAMENTO DE MATEMÁTICA
Correção parcial da Época Especial de exame de Matemática Discreta
I
Diga, justi…cando, se as seguintes proposições são verdadeiras ou falsas:
1. [1,0]244 1 mod 23.
Resolução: 23 é um número primo e 2 - 23; logo é possível aplicar o Teorema de Fermat
222
1 mod 23
então
244
222
2
1 mod 23
O que implica que a a…rmação é verdadeira.
2. [1,0]Dados conjuntos A e B, tem-se jAj + jBj = jA [ Bj + jA \ Bj.
Resolução: do princípio da inclusão-exclusão, aplicado aos dois conjuntos A e B, tem-se
jA [ Bj = jAj + jBj
jA \ Bj
Logo a a…rmação é verdadeira.
1 2 3 4 5 6 7
é sobrejectiva.
2 1 4 2 3 4 6
Resolução: a a…rmação é falsa, pois f (x) 6= 7, para todo o x 2 N7 .
3. [1,0]A função de N7 em N7 de…nida por f =
4. [1,0]Um grafo simples com n vértices e n 2 arestas é uma árvore.
Resolução: a a…rmação é falsa, pois uma árvore com n vértices tem, necessariamente,
n 1 arestas.
II
1. [1,5]Determine números inteiros x e y que satisfaçam a equação 28x + 36y = 44:
Resolução:
mdc (36; 28) = mdc (28; 8) =
36 = 1 28 + 8
= mdc (8; 4) = 4
28 = 3 8 + 4
Então
) 28
logo, sendo 44 = 4
28 1 + ( 3) 8 = 4 )
1 + ( 3) (36 + ( 1) 28) = 4 )
) 28 4 + 36 ( 3) = 4
11, tem-se x = 44 e y =
33.
2. [1,5]Determine, justi…cando, a menor solução positiva do seguinte sistema:
x
x
1 mod 12
:
1 mod 35
3. [2,0]Mostre que, se ajb e ajc, então aj(b2 + 3c).
Resolução: se ajb e ajc, então b = ka e c = la; logo b2 = k 2 a2 e 3c = 3la. Então
b2 + 3c = k 2 a2 + 3la = (k 2 a + 3l) a, ou seja, aj(b2 + 3c).
III
1. [2,0]Mostre, por indução em n, que
n
X
(k
1) k =
(n
k=1
1) n (n + 1)
3
2. Uma sequência binária de 0’s e 1’s com 8 dígitos (“bits”) designa-se por “byte”. Indique,
justi…cando:
(a) [0,5]O número de “bytes”que se podem obter;
Resolução: 2| {z
::: 2} = 28 = 256.
8
(b) [1,0]O número de “bytes”que começam por 10 e não terminam em 01:
Resolução: é necessário contar todas as sequências da forma 10abcdx, onde a; b; c; d 2
f0; 1g e x 2 f00; 10; 11g. Este é então dado por 24 3 = 48.
3. [1,5]Determine o coe…ciente de x8 y 5 no desenvolvimento de 6x +
Resolução: pelo teorema binomial
6x +
y
9
13
=
13
X
13
y
(6x)k
k
9
k=0
y 13
9
:
13 k
o coe…ciente procurado é então o do termo com k = 8, logo
13
y
(6x)8
8
9
sendo então o coe…ciente
13 68
8 95
5
=
13 68 8 5
xy
8 95
= 36 608.
IV
1. [1,0]Desenhe um grafo conexo com 6 vértices que seja regular e bipartido.
2. Considere o grafo ponderado G :
A
5
5
F
B
5
3
3
3
G
E
3
4
C
2
D
Justi…que detalhadamente as respostas às seguintes questões:
(a) [1,5]Utilize o algoritmo guloso com a ordenação dos vértices GAECBDF para obter
uma coloração dos vértices de G: Qual é o número cromático de G?
Resolução:
G
1 Inicialização
A
2 A e G são adjacentes
E
2 E é adjacente a G, mas não a A
C
2 C é adjacente a G, mas não a A
B
1 B é adjacente a C e A, mas não a G
D
1 D é adjacente a E e C, mas não a G
F
1 F é adjacente a A e E, mas não a G
Donde se conclui que
(G)
2; dado que G não é o grafo nulo, tem-se
(G) = 2.
(b) [1,0]Utilize o algoritmo de Kruskal para determinar uma árvore de suporte de custo
mínimo de G.
(c) [1,5] Utilize o algoritmo de Dijkstra para determinar um caminho de custo mínimo
entre os vértices A e D.
3. [1,0]Recorde que numa árvore existe um único caminho entre quaisquer dois vértices. Indique, justi…cando, o número de caminhos distintos existentes numa árvore com n vértices.
Resolução: dado que existe um único caminho entre quaisqueres dois vértices distintos,
e que um caminho determina unicamente os seus vértices extremos (que são distintos pela
hipótese do grafo em questão ser uma árvore), o número de caminhos é igual ao número
n (n 1)
.
de pares não-ordenados de dois vértices, isto é
2