ESTR_LISTA_08_GAB

Prévia do material em texto

UNICARIOCA
ESTRUTURA DE DADOS
LISTA-08
GABARITO
01- Encontre a matriz de adjacência para os grafos abaixo.
1
3
2
4
1 2 3 4
1 0 1 1 1
2 1 0 0 1
3 1 0 0 1
4 1 1 1 0
a)
01- Encontre a matriz de adjacência para os grafos abaixo.
1 2 3 4
1 0 1 1 1
2 1 0 0 1
3 1 0 1 2
4 1 1 2 0
b)
1
3
2
4
01- Encontre a matriz de adjacência para os grafos abaixo.
c)
1 2 3 4 5 6
1 1 1 0 0 1 0
2 1 0 1 0 1 0
3 0 1 0 1 0 0
4 0 0 1 0 1 1
5 1 1 0 1 0 0
6 0 0 0 1 0 1
01- Encontre a matriz de adjacência para os grafos abaixo.
d)
e3
e1
e2
e4
e5
e6
e7
U V W X Y 
U 0 1 1 0 0
V 1 0 1 1 1
W 1 1 0 1 0
X 0 1 1 0 1
Y 0 1 0 1 0
e) GRAFO DIRECIONADO - ORIENTADO
01- Encontre a matriz de adjacência para os grafos abaixo.
0 1 2 3 4 5
0 0 1 0 1 0 0
1 0 0 1 1 1 0
2 0 0 1 1 0 1
3 1 0 0 0 0 0
4 0 0 0 0 0 0
5 0 0 0 0 1 0
ESTRUTURA DE DADOS - LISTA_08 - GABARITO 1 MANUEL
02- Encontre a matriz de incidência dos seguintes grafos.
e1
e2
e3
e6
e5
e4
a)
e1 e2 e3 e4 e5 e6
v1 1 1 0 1 0 0
v2 1 1 2 0 1 0
v3 0 0 0 1 1 2
e1 e2 e3 e4 e5 e6
v1 1 0 0 2 0 0
v2 1 1 1 0 0 1
v3 0 1 1 0 1 0
v4 0 0 0 0 1 1
• •
••
v1 v2
v4
e1
e2 e3
e5
e6
e4
v3
b)
02- Encontre a matriz de incidência dos seguintes grafos.
03- Considere a matriz de adjacência abaixo de um grafo (G)
não direcionado.
1 2 3 4
1 0 1 1 1
2 1 0 0 1
3 1 0 0 1
4 1 1 1 1
Qual o grafo que corresponde a essa matriz de adjacência? 
1
3
2
4
a) b) 
1
3
2
4
03- Considere a matriz de adjacência abaixo de um grafo (G)
não direcionado.
1 2 3 4
1 0 1 1 1
2 1 0 0 1
3 1 0 0 1
4 1 1 1 1
Qual o grafo que corresponde a essa matriz de adjacência? 
c) d) 
1
3
2
4
1
3
2
4
03- Considere a matriz de adjacência abaixo de um grafo (G)
não direcionado.
1 2 3 4
1 0 1 1 1
2 1 0 0 1
3 1 0 0 1
4 1 1 1 1
Qual o grafo que corresponde a essa matriz de adjacência? 
e) 
1
3
2
4 GABARITO-D
04- A quantidade de grau total do grafo na figura é
A) 13
B) 14
C) 15
D) 16
E) 17
GABARITO-B
A - 2
B - 3
C - 3
D - 3
E - 3
TOTAL = 14
É A SOMA DOS GRAUS DOS NÓS!
ESTRUTURA DE DADOS - LISTA_08 - GABARITO 2 MANUEL
05-
O grafo acima pode ser representado pela seguinte matriz:
GABARITO-A
06- Considerando o grafo
ilustrado acima assinale a
opção em que é
apresentada a descrição
em vértices (V) e arestas
(A) V = {1, 2, 3, 4, 5, 6 } A = {(2, 4), (2, 3), (2, 5), (3, 6), (1, 5)}
(B) V = { 2, 4, 1, 3, 6, 5 } A = {(4, 2), (1, 3), (5, 2), (6, 3), (5, 3)}
(C) V = {1, 2, 3, 4, 5, 6 } A = {(4, 2), (3, 4), (5, 2), (6, 3), (5, 3)}
(D) V = {1, 2, 3, 4, 5, 6 } A = {(4, 2), (3, 1), (5, 1), (6, 2), (5, 3)}
(E) V = { 2, 4, 1, 3, 6, 5 } A = {(4, 2), (3, 1), (5, 2), (6, 3), (5, 3)}
(A) V = {1, 2, 3, 4, 5, 6 } A = {(2, 4), (2, 3), (2, 5), (3, 6), (1, 5)}
(B) V = { 2, 4, 1, 3, 6, 5 } A = {(4, 2), (1, 3), (5, 2), (6, 3), (5, 3)}
(C) V = {1, 2, 3, 4, 5, 6 } A = {(4, 2), (3, 4), (5, 2), (6, 3), (5, 3)}
(D) V = {1, 2, 3, 4, 5, 6 } A = {(4, 2), (3, 1), (5, 1), (6, 2), (5, 3)}
(E) V = { 2, 4, 1, 3, 6, 5 } A = {(4, 2), (3, 1), (5, 2), (6, 3), (5, 3)}
GABARITO-E
07- Considere que um grafo G seja constituído por um conjunto
(N) e por uma relação binária (A), tal que G = (N, A), em que os
elementos de N são denominados nós (ou vértices) e os
elementos de A são denominados arcos (ou arestas). Em face
dessas informações e do grafo abaixo, é correto afirmar que
esses conjuntos são N= {1,2,3,4} e A={(1,2),(2,1),(2,4),(2,3)}.
GABARITO - CERTO
08- Um grafo cujo nó de partida de um caminho coincide com o
nó de chegada caracteriza um grafo
(A) completo.
(B) cíclico.
(C) simétrico.
(D) conexo.
(E) regular.
CICLO - caminho de um vértice a ele mesmo de comprimento ≥ 3
GRAFO CÍCLICO: tem pelo menos um ciclo. 
Caso contrário é ACÍCLICO.
Um GRAFO CÍCLICO DIRIGIDO é uma
versão orientada de um grafo cíclico, com
todas as arestas sendo orientadas na
mesma direção.
GABARITO-B
08- Um grafo cujo nó de partida de um caminho coincide com o
nó de chegada caracteriza um grafo
(A) completo.
(B) cíclico.
(C) simétrico.
(D) conexo.
(E) regular.
Grafo ciclo ou grafo circular é um grafo que consiste de um
único ciclo, ou seja, um número de vértices conectados em uma
rede fechada. O grafo ciclo com n vértices é chamado Cn. O
número de vértices em um Cn se iguala ao número de arestas, e
cada vértice tem grau 2; isto é, cada vértice tem exatamente
duas arestas incidentes a ele.
ESTRUTURA DE DADOS - LISTA_08 - GABARITO 3 MANUEL
09- O grafo representado é um grafo
(A) conexo.
(B) fortemente conexo.
(C) não orientado.
(D) parcial.
(E) isolado.
Um grafo é fortemente conexo (strongly connected se para
qualquer par (v,w) de seus vértices existe um caminho de v a w
e também um caminho de w para v.
GABARITO-B
10- No grafo acima, cada vértice representa uma cidade, e os
números nas arestas representam a distância, em quilômetros,
entre as cidades. Considerando o menor caminho entre as
cidades A e K, assinale a opção que apresenta apenas
cidades que fazem parte desse menor caminho.
a) D e F
b) D e I
c) B e E
d) C e F
e) C e D
5+4+4+4 = 17
5+5+3+4 = 17
a) D e F
b) D e I
c) B e E
d) C e F
e) C e D
GABARITO-D
A base de tudo é o saber.
O saber te leva ao ter.
O saber te leva ao poder.
Não é desejável que o ter te leve ao
poder.
Mas, é inadmissível que o poder te
leve ao ter!
Francisco Clementino de San Tiago Dantas
Rio de Janeiro - 1911 / Rio de Janeiro 1964
ESTRUTURA DE DADOS - LISTA_08 - GABARITO 4 MANUEL