Quiz Grafos

Prévia do material em texto

08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 1/9
Name :
Class :
Date :
1. 
2. 
Quizizz
Grafos
O que é um Grafo?
a) Um grafo G é um par G
= ( V, E ) consistindo de
um conjunto não vazio
V e um conjunto E de
pares de elementos
não contidos em V
 b) Um grafo G é um par G
= ( V, E ) consistindo de
um conjunto vazio V e
um conjunto E de pares
de elementos contidos
em V
 
c) Um grafo G é um par G
= ( V, E ) consistindo de
um conjunto não vazio
V e um conjunto E de
pares de elementos
contidos em V
O que é um Laço?
a) Um laço é uma aresta
ou arco do tipo a=(v,u)
 b) Um laço é arco que
relaciona um vértice a
outro
 
c) Um laço é arco que
relaciona um vértice a
ele próprio.
08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 2/9
3. 
4. 
5. 
O que é um Multigrafo?
a) É aquele grafo que
possui mais de uma
linha conectando dois
vértices, mas que não
possui loops
 b) É aquele grafo que
possui mais de uma
linha conectando dois
vértices, mas que
possui loops
 
c) É aquele grafo que
possui uma linha
conectando dois
vértices, mas que não
possui loops
O que é Fonte?
a) É um vértice com grau
de entrada 0 e grau de
saída >= 1
 b) É um vértice v com
grauDeEmissão(v) = 0
 
c) ◦É um vértice v com
grauDeEmissão(v) >= 1
e grau de saída = 0
O que é Sumidouro?
a) É um vértice com grau
de entrada 0 e grau de
saída >= 1
 b) É um vértice v com
grauDeEmissão(v) = 0
 
c) ◦É um vértice v com
grauDeEmissão(v) >= 1
e grau de saída = 0
08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 3/9
6. 
7. 
8. 
9. 
O que é um Grafo Regular?
a) Um grafo é dito ser
regular quando todos
os seus vértices têm o
mesmo grau
 b) Um grafo é dito ser
regular quando todos
os seus vértices têm
grau par
 
c) Um grafo é dito ser
regular quando todos
os seus vértices têm
grau ímpar
O que é um Grafo Bipartido?
a) Um grafo G = (V, E) é
bipartido se V pode ser
dividido em dois
conjuntos V1 e V2 tal
que toda aresta de G
une um vértice de V1 a
outro de V2
 b) Um grafo G = (V, E) é
bipartido se V pode ser
dividido em dois
conjuntos V1 e V2 tal
que toda aresta de G
une um vértice de V1 a
outro de V1
 
c) ◦Um grafo G = (V, E) é
bipartido se V pode ser
dividido em dois
conjuntos V1 e V2 tal
que toda aresta de G
une um vértice de V2 a
outro de V2
O que é uma Cadeia Elementar?
a) Se não passa duas
vezes pelo mesmo
vértice
 b) Se não passa duas
vezes pela mesma
aresta
O que é uma Cadeia Simples?
a) Se não passa duas
vezes pelo mesmo
vértice
 b) Se não passa duas
vezes pela mesma
aresta
08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 4/9
10. 
11. 
12. 
13. 
O que é um Grafo Conexo?
a) Um grafo não orientado
é chamado de conexo
se existe um caminho
entre cada par de
vértices distintos do
grafo.
 b) É um grafo conectado
que não contém um
ciclo
 
c) É quando todos os
seus vértices têm o
mesmo grau
O que é um Grafo Biconectado?
a) São grafos que não
possuem nenhum
ponto de articulação
 b) São grafos que
possuem pelo menos
um ponto de
articulação
O que é uma Matriz de Incidência?
a) É uma matriz n x m. b) É uma matriz n x n.
O que é um Circuito Euleriano?
a) Um circuito é dito
euleriano se ele
contém todas as
arestas de um grafo
 b) Um circuito é dito
euleriano se ele
contém todas os
vértices de um grafo
08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 5/9
14. 
15. 
O que é um Grafo Euleriano?
a) É aquele que possui
um ciclo Euleriano.
 b) É euleriano se e
somente se G é conexo
e cada vértice V de tem
grau par
 
c) É euleriano se e
somente se G é conexo
e cada vértice V de tem
pelo menos um grau
par
O que é um Grafo Hamiltoniano?
a) É aquele que possui
um ciclo Hamiltoniano
 b) É hamiltoniano se e
somente se G é conexo
e cada vértice V de tem
grau par
 
c) É hamiltoniano se
possui um caminho
hamiltoniano, que
contenha todos os
vértices
08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 6/9
16. Sobre o funcionamento do algoritmo de Dijkstra. Qual alternativa explica seu
funcionamento?
a) Escolhe um vértice
como raiz da busca,
este algoritmo calcula o
custo mínimo deste
vértice para todos os
demais vértices do
grafo.
 b) Cria uma floresta F (um
conjunto de árvores),
onde cada vértice no
grafo é uma árvore
separada e um
conjunto S contendo
todas as arestas do
grafo.
 
c) Selecionar qualquer nó
e conectá-lo para o nó
mais próximo
identificar o nó
desconectado mais
próximo para um nó
conectado e então
conectar estes dois nós
08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 7/9
17. Sobre o funcionamento do algoritmo de Prim. Qual alternativa explica seu
funcionamento?
a) Escolhe um vértice
como raiz da busca,
este algoritmo calcula o
custo mínimo deste
vértice para todos os
demais vértices do
grafo.
 b) Cria uma floresta F (um
conjunto de árvores),
onde cada vértice no
grafo é uma árvore
separada e um
conjunto S contendo
todas as arestas do
grafo.
 
c) Selecionar qualquer nó
e conectá-lo para o nó
mais próximo
identificar o nó
desconectado mais
próximo para um nó
conectado e então
conectar estes dois nós
08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 8/9
18. Sobre o funcionamento do algoritmo de Kruskal. Qual alternativa explica seu
funcionamento?
a) Escolhe um vértice
como raiz da busca,
este algoritmo calcula o
custo mínimo deste
vértice para todos os
demais vértices do
grafo.
 b) Cria uma floresta F (um
conjunto de árvores),
onde cada vértice no
grafo é uma árvore
separada e um
conjunto S contendo
todas as arestas do
grafo.
 
c) Selecionar qualquer nó
e conectá-lo para o nó
mais próximo
identificar o nó
desconectado mais
próximo para um nó
conectado e então
conectar estes dois nós
08/06/2018 Quiz - Quizizz
https://quizizz.com/print/quiz/5b158ee1530794001ce651d4 9/9
Answer Key
1. c
2. c
3. a
4. a
5. b
6. a
7. a
8. a
9. b
10. a
11. a
12. a
13. a
14. b
15. a
16. a
17. c
18. b