TEORIA DOS GRAFOS

Prévia do material em texto

TEORIA DOS GRAFOS - 80h_Turma_01_112021 
 
Unidade1- Conceitos Básicos e Aplicações de Grafos 
 
 
Pergunta 1 
1. A teoria dos grafos começou em 1736 com um matemático suíço. Ele propôs 
uma solução para um problema utilizando grafos. Qual foi esse problema? 
 a. Problema das sete pontes de Konigsberg. 
 b. Problema dos 12 carros. 
 c. Nenhuma das alternativas anteriores. 
 d. Problema da atmosfera da terra. 
 e. Problema da forma de água. 
 
 
Pergunta 2 
1. Grafos são bastante utilizados para modelar e resolver problemas. Na 
modelagem de placas de circuitos eletrônicos, são utilizados grafos. Assinale a 
alternativa que explica corretamente como os grafos são utilizados nessa 
modelagem. 
 a. 
Uma placa de circuito eletrônica é composta por diversos componentes 
eletrônicos. Correntes elétricas percorrem por tais componentes. Dessa 
forma, grafos podem ser utilizados para representar o percurso das 
correntes entre os componentes, onde os componentes são representados 
pelas arestas, e os vértices representam a conexão entre os componentes. 
 
 b. 
Uma placa de circuito eletrônica é composta por diversos componentes 
eletrônicos. Correntes elétricas percorrem por tais componentes. Dessa 
forma, grafos podem ser utilizados para representar a utilização de tais 
placas em objetos eletrônicos. 
 
 c. 
Uma placa de circuito eletrônica é composta por diversos componentes 
eletrônicos. Correntes elétricas percorrem por tais componentes. Dessa 
forma, grafos podem ser utilizados para representar o percurso das 
correntes entre os componentes, onde os componentes são representados 
pelos vértices, e as arestas representam a conexão entre os componentes. 
 d. Placa de circuito eletrônica não utiliza grafos. 
 e. Nenhuma das alternativas anteriores. 
 
 
Pergunta 3 
1. Quem foi o primeiro a propor uma solução utilizando grafos? 
 a. Nikola Tesla. 
 b. Albert Einstein. 
 c. Isaac Newton. 
 d. Thomas Edison. 
 e. Leonhard Euler. 
 
Pergunta 4 
1. Leia as afirmações a seguir: 
I. Grafos são compostos por vértices e arestas; 
II. A Teoria dos grafos tem como enfoque principal o estudo da natureza; 
III. O objetivo da teoria dos grafos é estudar o relacionamento entre os objetos; 
IV. Grafos podem se compreendidos como estruturas do mundo real utilizadas 
na natureza. 
Analisando estas informações, é possível afirmar que: 
 a. Somente as afirmações I e III estão corretas. 
 b. Somente a afirmação I esta correta. 
 c. Somente as afirmações I e IV estão corretas. 
 d. Somente as afirmações II e III estão corretas. 
 e. Somente as afirmações I e II estão corretas. 
 
 
 
TEORIA DOS GRAFOS - 80h_Turma_01_112021 
 
Unidade 2 - Conceitos e Propriedades de Grafos 
 
Pergunta 1 
1. Observe o grafo abaixo e assinale a alternativa correta. 
 
 a. É um grafo bipartido. 
 b. Nenhuma das alternativas anteriores. 
 c. É um grafo orientado. 
 d. É um grafo simples. 
 e. É um grafo buquê. 
 
 
Pergunta 2 
1. O que são laços? 
 a. Arestas que ligam um grafo simples. 
 b. Arestas que ligam um vértice a ele mesmo. 
 c. Arestas que ligam um grafo bipartido. 
 d. Nenhuma das alternativas anteriores. 
 e. Arestas que ligam dois vértices diferentes. 
 
 
Pergunta 3 
1. Com relação ao grafo abaixo, ele é: 
 
 a. Buquê. 
 b. Vazio. 
 c. Trivial. 
 d. Hipergrafo. 
 e. Nulo. 
 
Pergunta 4 
1. O que são grafos rotulados? 
 a. Grafos nulos. 
 b. Grafos que possuem arestas paralelas. 
 c. Grafos triviais. 
 d. Grafos que possuem laços. 
 e. 
Grafos que possuem rótulos nos vértices ou 
arestas. 
 
 
TEORIA DOS GRAFOS - 80h_Turma_01_112021 
 
Unidade 3 - Planaridade e Conectividade 
 
Pergunta 1 
1. É CORRETO afirmar que um grafo é dito planar se 
 a. houver conexão em todos os vértices. 
 b. for um grafo K3,3. 
 c. 
admitir representação no plano de modo que exista cruzamento de 
vértices. 
 d. 
admitir uma representação no plano, de modo que neste não exista 
cruzamento de aresta. 
 e. 
admitir uma representação no plano de modo e que exista cruzamento 
de aresta. 
 
Pergunta 2 
1. O teorema de Kuratowski diz que um grafo G = (V, A) é 
 a. planar se e somente se G não contém uma subdivisão K3 ou K1,1. 
 b. conexo se e somente se G não contém uma subdivisão K5 ou K3,3. 
 c. planar se e somente se G não contém uma subdivisão K3 ou K4,4. 
 d. planar se e somente se G não contém uma subdivisão K5 ou K3,3. 
 e. colorido se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
Pergunta 3 
1. Um grafo G = (V, A) direcionado é dito fracamente conexo quando 
 a. 
existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
 b. 
não existe, pelo menos, um par de vértices i e j em G tal que o número 
de caminhos entre i e j seja menor que 2. 
 c. 
não existe, pelo menos, dois pares de vértices i e j em G tal que o 
número de caminhos entre i e j seja menor que 3. 
 d. 
existe, pelo menos, um par de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 1. 
 e. 
existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja maior que 1. 
 
Pergunta 4 
1. Coloração harmoniosa é uma coloração onde 
 a. 
cada par de cores aparece, no máximo, em um par de vértices adjacentes 
no grafo G. 
 b. 
as cores aparecem, no máximo, em dois pares de vértices adjacentes no 
grafo G. 
 c. 
cada par de cores aparece, no mínimo, em um par de vértices adjacentes 
no grafo G. 
 d. 
cada par de cores aparece, no mínimo, em um único vértice adjacente no 
grafo G. 
 e. 
cada par de cores aparece, no máximo, em dois pares de vértices 
adjacentes no grafo G. 
 
 
TEORIA DOS GRAFOS - 80h_Turma_01_112021 
 
Unidade 6 - Árvores e Ordenação Topológica 
 
Pergunta 1 
1. Leia atentamente as seguintes afirmações: 
I Floresta é um conjunto de árvores sem vértice em comum. 
II Floresta geradora contém todos os vértices de G. 
III Floresta geradora é um grafo que generaliza o conceito de árvore geradora. 
É VERDADEIRO o que se afirma em 
 a. III, apenas. 
 b. II e III, apenas. 
 c. I e II, apenas. 
 d. I, apenas. 
 e. II, apenas. 
 
 
Pergunta 2 
1. Na teoria de grafos, floresta é um conjunto de 
 a. arestas com vértices em comum. 
 b. árvores sem vértices em comum. 
 c. arestas sem vértices em comum. 
 d. árvores sem arestas em comum. 
 e. árvores com vértices em comum. 
 
Pergunta 3 
1. Fluxo em rede é o 
 a. ato de não transportar objetos por diversas redes. 
 b. mecanismo de não transportar objetos por uma rede. 
 c. ato de não transportar objetos por uma rede. 
 d. ato de transportar objetos por uma rede. 
 e. grafo de tamanho G. 
 
Pergunta 4 
1. Árvore geradora de um grafo G é um subgrafo gerador 
 a. conexo e acíclico. 
 b. desconexo em vértices e cíclico em arestas. 
 c. desconexo e cíclico. 
 d. desconexo e acíclico. 
 e. conexo e cíclico. 
 
AS I 
PERGUNTA 1
1.
0,15 pontos   
PERGUNTA 2
1.
0,15 pontos   
PERGUNTA 3
1.
0,15 pontos   
Leia as afirmações a seguir:
I. Grafos são compostos por vértices e arestas;
II. A Teoria dos grafos tem como enfoque principal o estudo da natureza;
III. O objetivo da teoria dos grafos é estudar o relacionamento entre os objetos;
IV. Grafos podem se compreendidos como estruturas do mundo real utilizadas na natureza.
Analisando estas informações, é possível afirmar que:
a. Somente as afirmações I e III estão corretas.
b. Somente a afirmação I esta correta.
c. Somente as afirmações I e IV estão corretas.
d. Somente as afirmações II e III estão corretas.
e. Somente as afirmações I e II estão corretas.
Quem foi o primeiro a propor uma solução utilizando grafos?
a. Nikola Tesla.
b. Isaac Newton.
c. Albert Einstein.
d. Thomas Edison.
e. Leonhard Euler.
A teoria dos grafos começou em 1736 com um matemático suíço. Ele propôs uma solução para um problema utilizando grafos. Qual foi 
esse problema?a. Problema dos 12 carros.
b. Nenhuma das alternativas anteriores.
c. Problema da forma de água.
d. Problema da atmosfera da terra.
e. Problema das sete pontes de Konigsberg.
PERGUNTA 4
1.
AS II
PERGUNTA 1
1.
0,15 pontos   
PERGUNTA 2
1.
0,15 pontos   
PERGUNTA 3
Segundo o texto, grafos podem ser utilizados em mapas de rodovias? Como?
a. Sim, grafos podem representar cidades por vértices, e as arestas podem representar as rodovias que ligam as cidades.
b. Não, grafos não podem ser utilizados em mapas de rodovias.
c. Sim, grafos podem representar as cidades por arestas, e os vértices podem representar as rodovias que ligam as cidades.
d. Nenhuma das alternativas anteriores.
e. Sim, grafos podem representar a população no mapa.
Com relação ao grafo abaixo, ele é:
a. Trivial.
b. Nulo.
c. Hipergrafo.
d. Vazio.
e. Buquê.
O que são grafos rotulados?
a. Grafos que possuem arestas paralelas.
b. Grafos nulos.
c. Grafos que possuem laços.
d. Grafos triviais.
e. Grafos que possuem rótulos nos vértices ou arestas.
1.
0,15 pontos   
PERGUNTA 4
1.
AS III
Observe o grafo abaixo e assinale a alternativa correta.
a. É um grafo bipartido.
b. É um grafo orientado.
c. É um grafo buquê.
d. É um grafo simples.
e. Nenhuma das alternativas anteriores.
Com relação ao grafo abaixo, ele é:
a. Pseudografo.
b. Multigrafo.
c. Reflexivo.
d. Simples.
e. Bipartido.
1.
0,175 pontos   
PERGUNTA 2
1.
0,175 pontos   
PERGUNTA 3
1.
0,175 pontos   
PERGUNTA 4
1.
Coloração harmoniosa é uma coloração onde
a. cada par de cores aparece, no mínimo, em um par de vértices adjacentes no grafo G.
b. cada par de cores aparece, no máximo, em um par de vértices adjacentes no grafo G.
c. as cores aparecem, no máximo, em dois pares de vértices adjacentes no grafo G.
d. cada par de cores aparece, no mínimo, em um único vértice adjacente no grafo G.
e. cada par de cores aparece, no máximo, em dois pares de vértices adjacentes no grafo G.
Um grafo G = (V, A) direcionado é dito fracamente conexo quando
a. existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos entre i e j seja menor que 2.
b. não existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos entre i e j seja menor que 3.
c. existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos entre i e j seja menor que 1.
d. existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos entre i e j seja maior que 1.
e. não existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos entre i e j seja menor que 2.
É CORRETO afirmar que um grafo é dito planar se
a. for um grafo K3,3.
b. admitir uma representação no plano, de modo que neste não exista cruzamento de aresta.
c. houver conexão em todos os vértices.
d. admitir representação no plano de modo que exista cruzamento de vértices.
e. admitir uma representação no plano de modo e que exista cruzamento de aresta.
Em um grafo G = (V, A)
a.
direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe caminho direcionado de i para j e de j para i em G. 
Agora, dois vértices i e j estão fortemente conectados em um grafo G = (V, A) não direcionado, se existem dois caminhos distintos 
em arestas de i para j em G.
b.
não direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe caminho direcionado de i para j e de j para i em
G. Agora, dois vértices i e j estão fortemente conectados em um grafo G = (V, A) direcionado, se existem dois caminhos distintos em 
arestas de i para j em G.
c.
direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe, pelo menos, dois caminhos direcionados de i para j
e de j para i em G. Agora, dois vértices i e j estão fortemente conectados em um grafo G = (V, A) não direcionado, se existe um 
caminho em arestas de i para j em G.
d.
direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe mais de um caminho direcionado de i para j e de j 
para i em G. Agora, dois vértices i e j estão fortemente conectados em um grafo G = (V, A) não direcionado, se existe um caminho 
distinto em arestas de i para j em G.
e.
não direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe n caminhos direcionados de i para j e de j para i
em G. Agora, dois vértices i e j estão fortemente conectados em um grafo G = (V, A) direcionado, se existe um caminho distinto em 
arestas de i para j em G.
AS IV
PERGUNTA 1
1.
0,175 pontos   
PERGUNTA 2
Tal como sugere o seu nome, o algoritmo busca em largura utiliza a técnica de busca em largura, cujo procedimento sempre
a. analisa os filhos e vizinhos do vértice verificado.
b. busca um caminho alternativo.
c. analisa o vértice final primeiro.
d. analisa os filhos do vértice verificado, apenas.
e. analisa os vizinhos do vértice verificado, apenas.
1.
0,175 pontos   
PERGUNTA 3
1.
0,175 pontos   
PERGUNTA 4
1.
Leia atentamente as seguintes afirmações:
I A ideia central implementada no algoritmo de busca em largura é analisar os vértices vizinhos do vértice em verificação.
II A ideia central implementada no algoritmo de busca em profundidade é analisar os vértices filhos do seu vértice pai.
III Tanto a busca em largura, como a busca em profundidade se baseiam em valores conhecidos no percussor.
É VERDADEIRO o que se afirma em
a. III, apenas.
b. I e II, apenas.
c. II, apenas.
d. I, apenas.
e. I, II e III.
Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso v seja descendente de w, então a aresta será
a. ponderada.
b. de avanço..
c. de cruzamento.
d. orientada.
e. de retorno.
O algoritmo de busca em profundidade sempre analisa os filhos do vértice verificado, o que cria uma árvore de
a. avanço.
b. profundidade.
c. cruzamento.
d. retorno.
e. largura.
A’S2 (1ºTENTATIVA) 
PERGUNTA 1 
1. O que são grafos ponderados? 
 
a. Grafos que possuem pesos associados em suas arestas ou vértices. 
 
b. Nenhuma das alternativas anteriores. 
 
c. Grafos nulos. 
 
d. Grafos que possuem buquê. 
 
e. Grafos que possuem laços. 
0,15 pontos 
PERGUNTA 2 
1. O que são grafos rotulados? 
 
a. Grafos que possuem laços. 
 
b. Grafos que possuem rótulos nos vértices ou arestas. 
 
c. Grafos que possuem arestas paralelas. 
 
d. Grafos nulos. 
 
e. Grafos triviais. 
0,15 pontos 
PERGUNTA 3 
1. Com relação ao grafo abaixo, ele é: 
 
 
a. Nulo. 
 
b. Vazio. 
 
c. Buquê. 
 
d. Hipergrafo. 
 
e. Trivial. 
0,15 pontos 
PERGUNTA 4 
1. Com relação ao grafo abaixo, ele é: 
 
 
a. Reflexivo. 
 
b. Multigrafo. 
 
c. Simples. 
 
d. Pseudografo. 
 
e. Bipartido. 
0,15 pontos 
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para 
salvar todas as respostas. 
 
 
A’S2(2ºTentativa) 
 
PERGUNTA 1 
1. Observe o grafo abaixo e assinale a alternativa correta. 
 
 
a. É um grafo orientado. 
 
b. É um grafo bipartido. 
 
c. É um grafo simples. 
 
d. É um grafo buquê. 
 
e. Nenhuma das alternativas anteriores. 
0,15 pontos 
PERGUNTA 2 
1. O que são laços? 
 
a. Nenhuma das alternativas anteriores. 
 
b. Arestas que ligam um grafo bipartido. 
 
c. Arestas que ligam um grafo simples. 
 
d. Arestas que ligam um vértice a ele mesmo. 
 
e. Arestas que ligam dois vértices diferentes. 
0,15 pontos 
PERGUNTA 3 
1. O que são grafos rotulados? 
 
a. Grafos que possuem arestas paralelas. 
 
b. Grafos que possuem rótulos nos vértices ou arestas. 
 
c. Grafos que possuem laços. 
 
d. Grafos nulos. 
 
e. Grafos triviais. 
0,15 pontos 
PERGUNTA 4 
1. Com relação ao grafo abaixo, ele é: 
 
 
a. Vazio. 
 
b. Hipergrafo. 
 
c. Nulo. 
 
d. Buquê. 
 
e. Trivial. 
0,15 pontos 
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para 
salvar todas as respostas. 
 
 
 
 
AS_III 
 
Fazer teste: AS III 
 
Informações do teste 
DescriçãoInstruções 
 
Várias tentativas Este teste permite 2 tentativas. Esta é a tentativa número 1. 
Forçar conclusão Este teste pode ser salvo e retomado posteriormente. 
 
Suas respostas foram salvas automaticamente. 
 Estado de Conclusão da Pergunta: 
PERGUNTA 1 
1. Um grafo G = (V, A) direcionado é dito fracamente conexo quando 
 
a. existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja maior que 1. 
 
b. existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
 
c. existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos 
entre i e j seja menor que 1. 
 
d. não existe, pelo menos, um par de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
 
e. não existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 3. 
0,175 pontos 
PERGUNTA 2 
1. Um grafo é denominado k-conexo quando para 
 
a. qualquer par de vértices de G existem, pelo menos, 3 caminhos iguais entre os 
quais. 
 
b. qualquer par de vértices de G existem, pelo menos, K caminhos diferentes entre 
os quais. 
 
c. todas as arestas de G existem, pelo menos, k-7 caminhos diferentes entre as 
quais. 
 
d. todos os pares de vértices de G existem, pelo menos, 2 caminhos diferentes 
entre os quais. 
 
e. todas as arestas de G existem, pelo menos, K caminhos iguais entre as quais. 
0,175 pontos 
PERGUNTA 3 
1. O teorema de Kuratowski diz que um grafo G = (V, A) é 
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724753_1&course_id=_731738_1&content_id=_10234260_1&step=null
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724753_1&course_id=_731738_1&content_id=_10234260_1&step=null
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724753_1&course_id=_731738_1&content_id=_10234260_1&step=null
 
a. planar se e somente se G não contém uma subdivisão K3 ou K4,4. 
 
b. planar se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
c. planar se e somente se G não contém uma subdivisão K3 ou K1,1. 
 
d. conexo se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
e. colorido se e somente se G não contém uma subdivisão K5 ou K3,3. 
0,175 pontos 
PERGUNTA 4 
1. Coloração harmoniosa é uma coloração onde 
 
a. as cores aparecem, no máximo, em dois pares de vértices adjacentes no grafo 
G. 
 
b. cada par de cores aparece, no máximo, em um par de vértices adjacentes no 
grafo G. 
 
c. cada par de cores aparece, no máximo, em dois pares de vértices adjacentes 
no grafo G. 
 
d. cada par de cores aparece, no mínimo, em um único vértice adjacente no grafo 
G. 
 
e. cada par de cores aparece, no mínimo, em um par de vértices adjacentes no 
grafo G. 
0,175 pontos 
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para 
salvar todas as respostas. 
 
Fazer teste: AS IV 
 
Informações do teste 
Descrição 
 
Instruções 
 
Várias tentativas Este teste permite 2 tentativas. Esta é a tentativa número 1. 
Forçar conclusão Este teste pode ser salvo e retomado posteriormente. 
 
Suas respostas foram salvas automaticamente. 
 Estado de Conclusão da Pergunta: 
PERGUNTA 1 
1. Leia atentamente as seguintes afirmações: 
I A ideia central implementada no algoritmo de busca em largura é analisar os vértices 
vizinhos do vértice em verificação. 
II A ideia central implementada no algoritmo de busca em profundidade é analisar os 
vértices filhos do seu vértice pai. 
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724752_1&course_id=_731738_1&content_id=_10234261_1&step=null
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724752_1&course_id=_731738_1&content_id=_10234261_1&step=null
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724752_1&course_id=_731738_1&content_id=_10234261_1&step=null
III Tanto a busca em largura, como a busca em profundidade se baseiam em valores 
conhecidos no percussor. 
É VERDADEIRO o que se afirma em 
 
a. I, apenas. 
 
b. I e II, apenas. 
 
c. I, II e III. 
 
d. II, apenas. 
 
e. III, apenas. 
0,175 pontos 
PERGUNTA 2 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
w seja descendente de v, então a aresta será 
 
a. orientada. 
 
b. de cruzamento. 
 
c. ponderada. 
 
d. de avanço.. 
 
e. de retorno. 
0,175 pontos 
PERGUNTA 3 
1. Tal como sugere o seu nome, o algoritmo busca em profundidade utiliza a técnica de 
profundidade, cujo procedimento sempre 
 
a. analisa os vizinhos do vértice verificado, apenas. 
 
b. busca um caminho alternativo. 
 
c. analisa os filhos e vizinhos do vértice verificado. 
 
d. analisa os filhos do vértice verificado, apenas. 
 
e. analisa o vértice final primeiro. 
0,175 pontos 
PERGUNTA 4 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
v seja descendente de w, então a aresta será 
 
a. ponderada. 
 
b. de avanço.. 
 
c. orientada. 
 
d. de cruzamento. 
 
e. de retorno. 
 
0,175 pontos 
 
Fazer teste: AS IV(2º Tentativa) 
 
PERGUNTA 1 
1. O algoritmo de busca em profundidade sempre analisa os filhos do vértice verificado, o 
que cria uma árvore de 
 
a. retorno. 
 
b. cruzamento. 
 
c. profundidade. 
 
d. largura. 
 
e. avanço. 
0,175 pontos 
PERGUNTA 2 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
w seja descendente de v, então a aresta será 
 
a. orientada. 
 
b. de avanço.. 
 
c. de retorno. 
 
d. de cruzamento. 
 
e. ponderada. 
0,175 pontos 
PERGUNTA 3 
1. Tal como sugere o seu nome, o algoritmo busca em largura utiliza a técnica de busca 
em largura, cujo procedimento sempre 
 
a. busca um caminho alternativo. 
 
b. analisa os filhos e vizinhos do vértice verificado. 
 
c. analisa os vizinhos do vértice verificado, apenas. 
 
d. analisa os filhos do vértice verificado, apenas. 
 
e. analisa o vértice final primeiro. 
0,175 pontos 
PERGUNTA 4 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
v seja descendente de w, então a aresta será 
 
a. de retorno. 
 
b. ponderada. 
 
c. de avanço.. 
 
d. orientada. 
 
e. de cruzamento. 
0,175 pontos 
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para 
salvar todas as respostas. 
 
 
Fazer teste: AS V 
 
Informações do teste 
Descrição 
 
Instruções 
 
Várias tentativas Este teste permite 2 tentativas. Esta é a tentativa número 1. 
Forçar conclusão Este teste pode ser salvo e retomado posteriormente. 
 
Suas respostas foram salvas automaticamente. 
 Estado de Conclusão da Pergunta: 
PERGUNTA 1 
1. Passeio em grafos consiste de uma sequência 
 
a. finita alternada de caminhos, que começa e termina por vértices. 
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724751_1&course_id=_731738_1&content_id=_10234262_1&step=null
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724751_1&course_id=_731738_1&content_id=_10234262_1&step=null
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724751_1&course_id=_731738_1&content_id=_10234262_1&step=null
 
b. finita alternada de caminhos, que começa e termina por vértices, tal que cada 
caminho começa no vértice inicial e termina no vértice final. 
 
c. finita alternada de vértices e arestas, que começa e termina por vértices, tal que 
cada aresta é incidente ao vértice que a precede e ao que a sucede. 
 
d. infinita de caminhos, que começa e termina por vértices, tal que cada caminho 
possui,no mínimo, um vértice. 
 
e. infinita de caminhos, que começa e termina por vértices, tal que cada caminho 
possui, no mínimo, dois vértices. 
0,175 pontos 
PERGUNTA 2 
1. Um grafo é denominado euleriano quando neste existe um ciclo que 
 
a. passa somente pelo vértice final. 
 
b. passa somente pelo vértice inicial. 
 
c. não passa por aresta alguma. 
 
d. não passa pelo vértice inicial. 
 
e. passa por todas as arestas de G sem repetição. 
0,175 pontos 
PERGUNTA 3 
1. Um grafo é denominado hamiltoniano quando neste existe um caminho que 
 
a. contém somente o vértice inicial. 
 
b. contém somente os vértices inicial e final. 
 
c. não passa por nenhum vértice. 
 
d. contém todos os vértices de G. 
 
e. contém somente o vértice final. 
0,175 pontos 
PERGUNTA 4 
1. O caminho mais curto entre dois vértices v e w de um grafo G ponderado é aquele cuja 
 
a. soma dos pesos das arestas possui o menor valor possível entre todos os 
caminhos entre v e w. 
 
b. soma dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
c. multiplicação dos pesos das arestas possui o maior valor possível entre todos 
os caminhos entre v e w. 
 
d. subtração dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
e. divisão dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
0,175 pontos 
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para 
salvar todas as respostas. 
 
Fazer teste: AS VI 
 
Informações do teste 
Descrição 
 
Instruções 
 
Várias tentativas Este teste permite 2 tentativas. Esta é a tentativa número 1. 
Forçar conclusão Este teste pode ser salvo e retomado posteriormente. 
 
Suas respostas foram salvas automaticamente. 
 Estado de Conclusão da Pergunta: 
PERGUNTA 1 
1. Leia atentamente as seguintes afirmações: 
I Árvore geradora de grau mínimo é uma árvore geradora desenvolvida em um grafo 
não ponderado e possuindo o menor grau máximo possível. 
II Árvore geradora mínima com mínimo grau é uma árvore geradora mínima de um 
grafo ponderado na qual possui o menor grau máximo possível. 
III Árvore geradora de grau mínimo e árvore geradora mínima com mínimo grau são 
sinônimos. 
É VERDADEIRO o que se afirma em 
 
a. II, apenas. 
 
b. III, apenas. 
 
c. II e III, apenas. 
 
d. I e II, apenas. 
 
e. II e III, apenas. 
0,175 pontos 
PERGUNTA 2 
1. Na teoria dos grafos, árvore geradora mínima é a árvore geradora de 
 
a. custo igual a todas as arestas de G. 
 
b. maior custo entre todas as possíveis em G. 
 
c. menor custo entre todas as possíveis em G. 
 
d. custo igual a todos os vértices de G. 
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724750_1&course_id=_731738_1&content_id=_10234263_1&step=null
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724750_1&course_id=_731738_1&content_id=_10234263_1&step=null
https://bb.cruzeirodosulvirtual.com.br/webapps/assessment/take/launch.jsp?course_assessment_id=_724750_1&course_id=_731738_1&content_id=_10234263_1&step=null
 
e. custo igual a todos os vértices e todas as arestas de G. 
0,175 pontos 
PERGUNTA 3 
1. Árvore geradora de um grafo G é um subgrafo gerador 
 
a. conexo e cíclico. 
 
b. desconexo e acíclico. 
 
c. conexo e acíclico. 
 
d. desconexo em vértices e cíclico em arestas. 
 
e. desconexo e cíclico. 
0,175 pontos 
PERGUNTA 4 
1. Na teoria de grafos, floresta é um conjunto de 
 
a. árvores sem vértices em comum. 
 
b. arestas com vértices em comum. 
 
c. árvores sem arestas em comum. 
 
d. árvores com vértices em comum. 
 
e. arestas sem vértices em comum. 
0,175 pontos 
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para 
salvar todas as respostas. 
 
 
 
 
 
 
 
AS V
PERGUNTA 1
1.
0,175 pontos   
PERGUNTA 2
1.
0,175 pontos   
PERGUNTA 3
1.
0,175 pontos   
PERGUNTA 4
1.
Um grafo é denominado euleriano quando neste existe um ciclo que
a. passa somente pelo vértice inicial.
b. não passa pelo vértice inicial.
c. passa somente pelo vértice final.
d. passa por todas as arestas de G sem repetição.
e. não passa por aresta alguma.
O caminho mais curto entre dois vértices v e w de um grafo G ponderado é aquele cuja
a. subtração dos pesos das arestas possui o maior valor possível entre todos os caminhos entre v e w.
b. divisão dos pesos das arestas possui o maior valor possível entre todos os caminhos entre v e w.
c. multiplicação dos pesos das arestas possui o maior valor possível entre todos os caminhos entre v e w.
d. soma dos pesos das arestas possui o maior valor possível entre todos os caminhos entre v e w.
e. soma dos pesos das arestas possui o menor valor possível entre todos os caminhos entre v e w.
Um grafo é denominado hamiltoniano quando neste existe um caminho que
a. contém somente o vértice final.
b. contém todos os vértices de G.
c. não passa por nenhum vértice.
d. contém somente os vértices inicial e final.
e. contém somente o vértice inicial.
Passeio em grafos consiste de uma sequência
a. infinita de caminhos, que começa e termina por vértices, tal que cada caminho possui, no mínimo, dois vértices.
b. finita alternada de caminhos, que começa e termina por vértices.
c.
finita alternada de caminhos, que começa e termina por vértices, tal que cada caminho começa no vértice inicial e
termina no vértice final.
d.
finita alternada de vértices e arestas, que começa e termina por vértices, tal que cada aresta é incidente ao 
vértice que a precede e ao que a sucede.
e. infinita de caminhos, que começa e termina por vértices, tal que cada caminho possui, no mínimo, um vértice.
AS VI
PERGUNTA 1
1.
0,175 pontos   
PERGUNTA 2
1.
0,175 pontos   
PERGUNTA 3
1.
0,175 pontos   
Na teoria dos grafos, árvore geradora mínima é a árvore geradora de
a. custo igual a todas as arestas de G.
b. menor custo entre todas as possíveis em G.
c. custo igual a todos os vértices e todas as arestas de G.
d. maior custo entre todas as possíveis em G.
e. custo igual a todos os vértices de G.
Leia atentamente as seguintes afirmações:
I Floresta é um conjunto de árvores sem vértice em comum.
II Floresta geradora contém todos os vértices de G.
III Floresta geradora é um grafo que generaliza o conceito de árvore geradora.
É VERDADEIRO o que se afirma em
a. I e II, apenas.
b. II, apenas.
c. I, apenas.
d. III, apenas.
e. II e III, apenas.
Na teoria de grafos, floresta é um conjunto de
a. árvores com vértices em comum.
b. arestas com vértices em comum.
c. árvores sem arestas em comum.
d. árvores sem vértices em comum.
e. arestas sem vértices em comum.
PERGUNTA 4
1. Árvore geradora de um grafo G é um subgrafo gerador
a. desconexo em vértices e cíclico em arestas.
b. desconexo e acíclico.
c. conexo e acíclico.
d. desconexo e cíclico.
e. conexo e cíclico.
ASI 
PERGUNTA 1 
1. A teoria dos grafos começou em 1736 com um matemático suíço. Ele propôs uma 
solução para um problema utilizando grafos. Qual foi esse problema? 
 
a. Problema dos 12 carros. 
 
b. Nenhuma das alternativas anteriores. 
 
c. Problema da forma de água. 
 
d. Problema das sete pontes de Konigsberg. 
 
e. Problema da atmosfera da terra. 
0,15 pontos 
PERGUNTA 2 
1. Quem foi o primeiro a propor uma solução utilizando grafos? 
 
a. Thomas Edison. 
 
b. Nikola Tesla. 
 
c. Albert Einstein. 
 
d. Isaac Newton. 
 
e. Leonhard Euler. 
0,15 pontos 
PERGUNTA 3 
1. Leia as afirmações a seguir: 
I. Grafos são compostos por vértices e arestas; 
II. A Teoria dos grafos tem como enfoque principal o estudo da natureza; 
III. O objetivo da teoria dos grafos é estudar o relacionamento entre os objetos; 
IV. Grafos podem se compreendidos como estruturas do mundo real utilizadas na 
natureza. 
Analisando estas informações, é possívelafirmar que: 
 
a. Somente as afirmações I e III estão corretas. 
 
b. Somente as afirmações II e III estão corretas. 
 
c. Somente as afirmações I e IV estão corretas. 
 
d. Somente as afirmações I e II estão corretas. 
 
e. Somente a afirmação I esta correta. 
0,15 pontos 
PERGUNTA 4 
1. O desenho a seguir é considerado um grafo? Se sim, quantos vértices e arestas ele 
possui? 
 
 
a. Não, o desenho acima não é um grafo. 
 
b. Sim, o desenho acima é um grafo de 4 vértices e 3 arestas. 
 
c. Sim, o desenho acima é um grafo de 4 vértices e 6 arestas. 
 
d. Sim, o desenho acima é um grafo de 6 vértices e 4 arestas. 
 
e. Sim, o desenho acima é um grafo de 2 vértices e 3 arestas. 
0,15 pontos 
ASI I 
PERGUNTA 1 
1. O que são grafos ponderados? 
 
a. Grafos que possuem pesos associados em suas arestas ou vértices. 
 
b. Grafos que possuem laços. 
 
c. Grafos nulos. 
 
d. Grafos que possuem buquê. 
 
e. Nenhuma das alternativas anteriores. 
0,15 pontos 
PERGUNTA 2 
1. O que são laços? 
 
a. Nenhuma das alternativas anteriores. 
 
b. Arestas que ligam dois vértices diferentes. 
 
c. Arestas que ligam um grafo bipartido. 
 
d. Arestas que ligam um vértice a ele mesmo. 
 
e. Arestas que ligam um grafo simples. 
0,15 pontos 
PERGUNTA 3 
1. Com relação ao grafo abaixo, ele é: 
 
 
a. Bipartido. 
 
b. Reflexivo. 
 
c. Pseudografo. 
 
d. Multigrafo. 
 
e. Simples. 
0,15 pontos 
PERGUNTA 4 
1. O que são grafos rotulados? 
 
a. Grafos que possuem arestas paralelas. 
 
b. Grafos que possuem laços. 
 
c. Grafos nulos. 
 
d. Grafos triviais. 
 
e. Grafos que possuem rótulos nos vértices ou arestas. 
0,15 pontos 
 
AS I I I 
PERGUNTA 1 
1. Coloração harmoniosa é uma coloração onde 
 
a. cada par de cores aparece, no máximo, em um par de vértices adjacentes no 
grafo G. 
 
b. cada par de cores aparece, no mínimo, em um par de vértices adjacentes no 
grafo G. 
 
c. as cores aparecem, no máximo, em dois pares de vértices adjacentes no grafo 
G. 
 
d. cada par de cores aparece, no máximo, em dois pares de vértices adjacentes 
no grafo G. 
 
e. cada par de cores aparece, no mínimo, em um único vértice adjacente no grafo 
G. 
0,175 pontos 
PERGUNTA 2 
1. Um grafo é denominado k-conexo quando para 
 
a. qualquer par de vértices de G existem, pelo menos, K caminhos diferentes entre 
os quais. 
 
b. todas as arestas de G existem, pelo menos, K caminhos iguais entre as quais. 
 
c. todos os pares de vértices de G existem, pelo menos, 2 caminhos diferentes 
entre os quais. 
 
d. qualquer par de vértices de G existem, pelo menos, 3 caminhos iguais entre os 
quais. 
 
e. todas as arestas de G existem, pelo menos, k-7 caminhos diferentes entre as 
quais. 
0,175 pontos 
PERGUNTA 3 
1. É CORRETO afirmar que um grafo é dito planar se 
 
a. houver conexão em todos os vértices. 
 
b. admitir representação no plano de modo que exista cruzamento de vértices. 
 
c. for um grafo K3,3. 
 
d. admitir uma representação no plano de modo e que exista cruzamento de 
aresta. 
 
e. admitir uma representação no plano, de modo que neste não exista cruzamento 
de aresta. 
0,175 pontos 
PERGUNTA 4 
1. Um grafo G = (V, A) direcionado é dito fracamente conexo quando 
 
a. não existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 3. 
 
b. existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos 
entre i e j seja menor que 1. 
 
c. existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
 
d. existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja maior que 1. 
 
e. não existe, pelo menos, um par de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
 
AS IV 
PERGUNTA 1 
1. Tal como sugere o seu nome, o algoritmo busca em largura utiliza a técnica de busca 
em largura, cujo procedimento sempre 
 
a. busca um caminho alternativo. 
 
b. analisa os filhos do vértice verificado, apenas. 
 
c. analisa os vizinhos do vértice verificado, apenas. 
 
d. analisa os filhos e vizinhos do vértice verificado. 
 
e. analisa o vértice final primeiro. 
0,175 pontos 
PERGUNTA 2 
1. O algoritmo de busca em profundidade sempre analisa os filhos do vértice verificado, o 
que cria uma árvore de 
 
a. retorno. 
 
b. cruzamento. 
 
c. profundidade. 
 
d. avanço. 
 
e. largura. 
0,175 pontos 
PERGUNTA 3 
1. Leia atentamente as seguintes afirmações: 
I A ideia central implementada no algoritmo de busca em largura é analisar os vértices 
vizinhos do vértice em verificação. 
II A ideia central implementada no algoritmo de busca em profundidade é analisar os 
vértices filhos do seu vértice pai. 
III Tanto a busca em largura, como a busca em profundidade se baseiam em valores 
conhecidos no percussor. 
É VERDADEIRO o que se afirma em 
 
a. II, apenas. 
 
b. I, II e III. 
 
c. I, apenas. 
 
d. I e II, apenas. 
 
e. III, apenas. 
0,175 pontos 
PERGUNTA 4 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
v seja descendente de w, então a aresta será 
 
a. de cruzamento. 
 
b. de retorno. 
 
c. ponderada. 
 
d. de avanço. 
 
e. orientada. 
0,175 pontos 
 
AS V 
PERGUNTA 1 
1. Um caminho mais curto entre dois vértices v e w de um grafo G NÃO ponderado é 
aquele 
 
a. que acumula a quantidade de zero aresta entre v e w. 
 
b. no qual não há caminho entre as arestas v e w. 
 
c. que acumula a maior quantidade de arestas entre v e w. 
 
d. que acumula a quantidade de três arestas entre v e w. 
 
e. que acumula a menor quantidade de arestas entre v e w. 
0,175 pontos 
PERGUNTA 2 
1. Um grafo é denominado hamiltoniano quando neste existe um caminho que 
 
a. contém somente os vértices inicial e final. 
 
b. contém somente o vértice inicial. 
 
c. contém todos os vértices de G. 
 
d. contém somente o vértice final. 
 
e. não passa por nenhum vértice. 
0,175 pontos 
PERGUNTA 3 
1. O caminho mais curto entre dois vértices v e w de um grafo G ponderado é aquele cuja 
 
a. divisão dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
b. soma dos pesos das arestas possui o menor valor possível entre todos os 
caminhos entre v e w. 
 
c. soma dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
d. multiplicação dos pesos das arestas possui o maior valor possível entre todos 
os caminhos entre v e w. 
 
e. subtração dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
0,175 pontos 
PERGUNTA 4 
1. Um caminho em grafos pode ser definido como uma sequência de 
 
a. passeios, tal que para cada passeio há mais de um vértice. 
 
b. passeios, tal que para cada passeio há uma aresta para o vértice inicial. 
 
c. passeios, tal que para cada passeio há uma aresta para o vértice inicial e outra 
para o vértice final. 
 
d. passeios, tal que para cada passeio há uma aresta para o vértice final. 
 
e. vértices, tal que para cada vértice da sequência há uma aresta para o próximo 
vértice da sequência. 
0,175 pontos 
 
AS VI 
 
PERGUNTA 1 
1. Fluxo em rede é o 
 
a. ato de não transportar objetos por diversas redes. 
 
b. ato de não transportar objetos por uma rede. 
 
c. grafo de tamanho G. 
 
d. mecanismo de não transportar objetos por uma rede. 
 
e. ato de transportar objetos por uma rede. 
0,175 pontos 
PERGUNTA 2 
1. Leia atentamente as seguintes afirmações: 
I Floresta é um conjunto de árvores sem vértice em comum. 
II Floresta geradora contém todos os vértices de G. 
III Floresta geradora é um grafo que generaliza o conceito de árvore geradora. 
É VERDADEIRO o que se afirma em 
 
a. I e II, apenas. 
 
b. II, apenas. 
 
c. III, apenas. 
 
d. I, apenas. 
 
e. II e III,apenas. 
0,175 pontos 
PERGUNTA 3 
1. Na teoria dos grafos, árvore geradora mínima é a árvore geradora de 
 
a. menor custo entre todas as possíveis em G. 
 
b. maior custo entre todas as possíveis em G. 
 
c. custo igual a todos os vértices e todas as arestas de G. 
 
d. custo igual a todas as arestas de G. 
 
e. custo igual a todos os vértices de G. 
0,175 pontos 
PERGUNTA 4 
1. Leia atentamente as seguintes afirmações: 
I Árvore geradora de grau mínimo é uma árvore geradora desenvolvida em um grafo 
não ponderado e possuindo o menor grau máximo possível. 
II Árvore geradora mínima com mínimo grau é uma árvore geradora mínima de um 
grafo ponderado na qual possui o menor grau máximo possível. 
III Árvore geradora de grau mínimo e árvore geradora mínima com mínimo grau são 
sinônimos. 
É VERDADEIRO o que se afirma em 
 
a. I e II, apenas. 
 
b. III, apenas. 
 
c. II e III, apenas. 
 
d. II e III, apenas. 
 
e. II, apenas. 
0,175 pontos 
 
PER GUNTA 1 
1. Leia atentamente as seguintes afirmações: 
I Floresta é um conjunto de árvores sem vértice em comum. 
II Floresta geradora contém todos os vértices de G. 
III Floresta geradora é um grafo que generaliza o conceito de árvore geradora. 
É VERDADEIRO o que se afirma em 
 
a. II, apenas. 
 
b. I e II, apenas. 
 
c. III, apenas. 
 
d. I, apenas. 
 
e. II e III, apenas. 
0,175 pontos 
PER GUNTA 2 
1. Leia atentamente as seguintes afirmações: 
I Árvore geradora de grau mínimo é uma árvore geradora desenvolvida em um grafo 
não ponderado e possuindo o menor grau máximo possível. 
II Árvore geradora mínima com mínimo grau é uma árvore geradora mínima de um 
grafo ponderado na qual possui o menor grau máximo possível. 
III Árvore geradora de grau mínimo e árvore geradora mínima com mínimo grau são 
sinônimos. 
É VERDADEIRO o que se afirma em 
 
a. III, apenas. 
 
b. II e III, apenas. 
 
c. II e III, apenas. 
 
d. I e II, apenas. 
 
e. II, apenas. 
0,175 pontos 
PER GUNTA 3 
1. Fluxo em rede é o 
 
a. grafo de tamanho G. 
 
b. ato de não transportar objetos por diversas redes. 
 
c. ato de transportar objetos por uma rede. 
 
d. ato de não transportar objetos por uma rede. 
 
e. mecanismo de não transportar objetos por uma rede. 
0,175 pontos 
PER GUNTA 4 
1. Árvore geradora de um grafo G é um subgrafo gerador 
 
a. desconexo em vértices e cíclico em arestas. 
 
b. conexo e cíclico. 
 
c. desconexo e acíclico. 
 
d. conexo e acíclico. 
 
e. desconexo e cíclico. 
 
PER GUNTA 1 
1. Um grafo é denominado hamiltoniano quando neste existe um caminho que 
 
a. contém somente o vértice inicial. 
 
b. não passa por nenhum vértice. 
 
c. contém somente o vértice final. 
 
d. contém somente os vértices inicial e final. 
 
e. contém todos os vértices de G. 
0,175 pontos 
PER GUNTA 2 
1. Um grafo é denominado euleriano quando neste existe um ciclo que 
 
a. passa somente pelo vértice final. 
 
b. passa somente pelo vértice inicial. 
 
c. não passa pelo vértice inicial. 
 
d. não passa por aresta alguma. 
 
e. passa por todas as arestas de G sem repetição. 
0,175 pontos 
PER GUNTA 3 
1. O caminho mais curto entre dois vértices v e w de um grafo G ponderado é aquele cuja 
 
a. soma dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
b. divisão dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
c. subtração dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
d. multiplicação dos pesos das arestas possui o maior valor possível entre todos 
os caminhos entre v e w. 
 
e. soma dos pesos das arestas possui o menor valor possível entre todos os 
caminhos entre v e w. 
0,175 pontos 
PER GUNTA 4 
1. Um caminho mais curto entre dois vértices v e w de um grafo G NÃO ponderado é 
aquele 
 
a. que acumula a quantidade de zero aresta entre v e w. 
 
b. no qual não há caminho entre as arestas v e w. 
 
c. que acumula a quantidade de três arestas entre v e w. 
 
d. que acumula a menor quantidade de arestas entre v e w. 
 
e. que acumula a maior quantidade de arestas entre v e w. 
 
 
PER GUNTA 1 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
v seja descendente de w, então a aresta será 
 
a. de cruzamento. 
 
b. ponderada. 
 
c. orientada. 
 
d. de retorno. 
 
e. de avanço.. 
0,175 pontos 
PER GUNTA 2 
1. Tal como sugere o seu nome, o algoritmo busca em profundidade utiliza a técnica de 
profundidade, cujo procedimento sempre 
 
a. analisa os vizinhos do vértice verificado, apenas. 
 
b. busca um caminho alternativo. 
 
c. analisa o vértice final primeiro. 
 
d. analisa os filhos do vértice verificado, apenas. 
 
e. analisa os filhos e vizinhos do vértice verificado. 
0,175 pontos 
PER GUNTA 3 
1. Leia atentamente as seguintes afirmações: 
I A ideia central implementada no algoritmo de busca em largura é analisar os vértices 
vizinhos do vértice em verificação. 
II A ideia central implementada no algoritmo de busca em profundidade é analisar os 
vértices filhos do seu vértice pai. 
III Tanto a busca em largura, como a busca em profundidade se baseiam em valores 
conhecidos no percussor. 
É VERDADEIRO o que se afirma em 
 
a. I, apenas. 
 
b. I, II e III. 
 
c. II, apenas. 
 
d. I e II, apenas. 
 
e. III, apenas. 
0,175 pontos 
PER GUNTA 4 
1. O algoritmo de busca em profundidade sempre analisa os filhos do vértice verificado, o 
que cria uma árvore de 
 
a. retorno. 
 
b. avanço. 
 
c. cruzamento. 
 
d. largura. 
 
e. profundidade. 
 
 
PER GUNTA 1 
1. Um grafo G = (V, A) direcionado é dito fracamente conexo quando 
 
a. existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos 
entre i e j seja menor que 1. 
 
b. não existe, pelo menos, um par de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
 
c. existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja maior que 1. 
 
d. não existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 3. 
 
e. existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
0,175 pontos 
PER GUNTA 2 
1. É CORRETO afirmar que um grafo é dito planar se 
 
a. admitir uma representação no plano de modo e que exista cruzamento de 
aresta. 
 
b. admitir uma representação no plano, de modo que neste não exista cruzamento 
de aresta. 
 
c. houver conexão em todos os vértices. 
 
d. for um grafo K3,3. 
 
e. admitir representação no plano de modo que exista cruzamento de vértices. 
0,175 pontos 
PER GUNTA 3 
1. O teorema de Kuratowski diz que um grafo G = (V, A) é 
 
a. planar se e somente se G não contém uma subdivisão K3 ou K1,1. 
 
b. planar se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
c. planar se e somente se G não contém uma subdivisão K3 ou K4,4. 
 
d. colorido se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
e. conexo se e somente se G não contém uma subdivisão K5 ou K3,3. 
0,175 pontos 
PER GUNTA 4 
1. Em um grafo G = (V, A) 
 
a. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe 
caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e j 
estão fortemente conectados em um grafo G = (V, A) não direcionado, se 
existem dois caminhos distintos em arestas de i para j em G. 
 
b. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe 
mais de um caminho direcionado de i para j e de j para i em G. Agora, dois 
vértices i e j estão fortemente conectados em um grafo G = (V, A) não 
direcionado, se existe um caminho distinto em arestas de i para j em G. 
 
c. direcionado, é dito que dois vértices i e j estão fortemente conectados, se 
existe, pelo menos,dois caminhos direcionados de i para j e de j para i em G. 
Agora, dois vértices i e j estão fortemente conectados em um grafo G = (V, A) 
não direcionado, se existe um caminho em arestas de i para j em G. 
 
d. não direcionado, é dito que dois vértices i e j estão fortemente conectados, se 
existe caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e 
j estão fortemente conectados em um grafo G = (V, A) direcionado, se existem 
dois caminhos distintos em arestas de i para j em G. 
 
e. não direcionado, é dito que dois vértices i e j estão fortemente conectados, se 
existe n caminhos direcionados de i para j e de j para i em G. Agora, dois 
vértices i e j estão fortemente conectados em um grafo G = (V, A) direcionado, 
se existe um caminho distinto em arestas de i para j em G. 
 
 
PER GUNTA 1 
1. O que são laços? 
 
a. Arestas que ligam um grafo bipartido. 
 
b. Arestas que ligam dois vértices diferentes. 
 
c. Arestas que ligam um grafo simples. 
 
d. Nenhuma das alternativas anteriores. 
 
e. Arestas que ligam um vértice a ele mesmo. 
0,15 pontos 
PER GUNTA 2 
1. Observe o grafo abaixo e assinale a alternativa correta. 
 
 
a. Nenhuma das alternativas anteriores. 
 
b. É um grafo simples. 
 
c. É um grafo buquê. 
 
d. É um grafo bipartido. 
 
e. É um grafo orientado. 
0,15 pontos 
PER GUNTA 3 
1. O que são grafos rotulados? 
 
a. Grafos que possuem rótulos nos vértices ou arestas. 
 
b. Grafos nulos. 
 
c. Grafos triviais. 
 
d. Grafos que possuem arestas paralelas. 
 
e. Grafos que possuem laços. 
0,15 pontos 
PER GUNTA 4 
1. Com relação ao grafo abaixo, ele é: 
 
 
a. Buquê. 
 
b. Trivial. 
 
c. Hipergrafo. 
 
d. Nulo. 
 
e. Vazio. 
 
 
PER GUNTA 1 
1. Leia as afirmações a seguir: 
I. Grafos são compostos por vértices e arestas; 
II. A Teoria dos grafos tem como enfoque principal o estudo da natureza; 
III. O objetivo da teoria dos grafos é estudar o relacionamento entre os objetos; 
IV. Grafos podem se compreendidos como estruturas do mundo real utilizadas na 
natureza. 
Analisando estas informações, é possível afirmar que: 
 
a. Somente as afirmações I e III estão corretas. 
 
b. Somente as afirmações I e II estão corretas. 
 
c. Somente a afirmação I esta correta. 
 
d. Somente as afirmações I e IV estão corretas. 
 
e. Somente as afirmações II e III estão corretas. 
0,15 pontos 
PER GUNTA 2 
1. Segundo o texto, grafos podem ser utilizados em mapas de rodovias? Como? 
 
a. Sim, grafos podem representar a população no mapa. 
 
b. Nenhuma das alternativas anteriores. 
 
c. Sim, grafos podem representar as cidades por arestas, e os vértices podem 
representar as rodovias que ligam as cidades. 
 
d. Sim, grafos podem representar cidades por vértices, e as arestas podem 
representar as rodovias que ligam as cidades. 
 
e. Não, grafos não podem ser utilizados em mapas de rodovias. 
0,15 pontos 
PER GUNTA 3 
1. O desenho a seguir é considerado um grafo? Se sim, quantos vértices e arestas ele 
possui? 
 
 
a. Não, o desenho acima não é um grafo. 
 
b. Sim, o desenho acima é um grafo de 6 vértices e 4 arestas. 
 
c. Sim, o desenho acima é um grafo de 4 vértices e 6 arestas. 
 
d. Sim, o desenho acima é um grafo de 2 vértices e 3 arestas. 
 
e. Sim, o desenho acima é um grafo de 4 vértices e 3 arestas. 
0,15 pontos 
PER GUNTA 4 
1. A teoria dos grafos começou em 1736 com um matemático suíço. Ele propôs uma 
solução para um problema utilizando grafos. Qual foi esse problema? 
 
a. Problema da atmosfera da terra. 
 
b. Problema das sete pontes de Konigsberg. 
 
c. Problema da forma de água. 
 
d. Nenhuma das alternativas anteriores. 
 
e. Problema dos 12 carros. 
 
PER GUNTA 1 
1. Leia atentamente as seguintes afirmações: 
I Floresta é um conjunto de árvores sem vértice em comum. 
II Floresta geradora contém todos os vértices de G. 
III Floresta geradora é um grafo que generaliza o conceito de árvore geradora. 
É VERDADEIRO o que se afirma em 
 
a. II, apenas. 
 
b. I e II, apenas. 
 
c. III, apenas. 
 
d. I, apenas. 
 
e. II e III, apenas. 
0,175 pontos 
PER GUNTA 2 
1. Leia atentamente as seguintes afirmações: 
I Árvore geradora de grau mínimo é uma árvore geradora desenvolvida em um grafo 
não ponderado e possuindo o menor grau máximo possível. 
II Árvore geradora mínima com mínimo grau é uma árvore geradora mínima de um 
grafo ponderado na qual possui o menor grau máximo possível. 
III Árvore geradora de grau mínimo e árvore geradora mínima com mínimo grau são 
sinônimos. 
É VERDADEIRO o que se afirma em 
 
a. III, apenas. 
 
b. II e III, apenas. 
 
c. II e III, apenas. 
 
d. I e II, apenas. 
 
e. II, apenas. 
0,175 pontos 
PER GUNTA 3 
1. Fluxo em rede é o 
 
a. grafo de tamanho G. 
 
b. ato de não transportar objetos por diversas redes. 
 
c. ato de transportar objetos por uma rede. 
 
d. ato de não transportar objetos por uma rede. 
 
e. mecanismo de não transportar objetos por uma rede. 
0,175 pontos 
PER GUNTA 4 
1. Árvore geradora de um grafo G é um subgrafo gerador 
 
a. desconexo em vértices e cíclico em arestas. 
 
b. conexo e cíclico. 
 
c. desconexo e acíclico. 
 
d. conexo e acíclico. 
 
e. desconexo e cíclico. 
 
PER GUNTA 1 
1. Um grafo é denominado hamiltoniano quando neste existe um caminho que 
 
a. contém somente o vértice inicial. 
 
b. não passa por nenhum vértice. 
 
c. contém somente o vértice final. 
 
d. contém somente os vértices inicial e final. 
 
e. contém todos os vértices de G. 
0,175 pontos 
PER GUNTA 2 
1. Um grafo é denominado euleriano quando neste existe um ciclo que 
 
a. passa somente pelo vértice final. 
 
b. passa somente pelo vértice inicial. 
 
c. não passa pelo vértice inicial. 
 
d. não passa por aresta alguma. 
 
e. passa por todas as arestas de G sem repetição. 
0,175 pontos 
PER GUNTA 3 
1. O caminho mais curto entre dois vértices v e w de um grafo G ponderado é aquele cuja 
 
a. soma dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
b. divisão dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
c. subtração dos pesos das arestas possui o maior valor possível entre todos os 
caminhos entre v e w. 
 
d. multiplicação dos pesos das arestas possui o maior valor possível entre todos 
os caminhos entre v e w. 
 
e. soma dos pesos das arestas possui o menor valor possível entre todos os 
caminhos entre v e w. 
0,175 pontos 
PER GUNTA 4 
1. Um caminho mais curto entre dois vértices v e w de um grafo G NÃO ponderado é 
aquele 
 
a. que acumula a quantidade de zero aresta entre v e w. 
 
b. no qual não há caminho entre as arestas v e w. 
 
c. que acumula a quantidade de três arestas entre v e w. 
 
d. que acumula a menor quantidade de arestas entre v e w. 
 
e. que acumula a maior quantidade de arestas entre v e w. 
 
 
PER GUNTA 1 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
v seja descendente de w, então a aresta será 
 
a. de cruzamento. 
 
b. ponderada. 
 
c. orientada. 
 
d. de retorno. 
 
e. de avanço.. 
0,175 pontos 
PER GUNTA 2 
1. Tal como sugere o seu nome, o algoritmo busca em profundidade utiliza a técnica de 
profundidade, cujo procedimento sempre 
 
a. analisa os vizinhos do vértice verificado, apenas. 
 
b. busca um caminho alternativo. 
 
c. analisa o vértice final primeiro. 
 
d. analisa os filhos do vértice verificado, apenas. 
 
e. analisa os filhos e vizinhos do vértice verificado. 
0,175 pontos 
PER GUNTA 3 
1. Leia atentamente as seguintes afirmações: 
I A ideia central implementada no algoritmo de busca em largura é analisar os vértices 
vizinhos do vértice em verificação. 
II A ideia central implementada no algoritmo de busca em profundidade é analisar os 
vértices filhos do seu vértice pai. 
III Tanto a busca em largura, como a busca emprofundidade se baseiam em valores 
conhecidos no percussor. 
É VERDADEIRO o que se afirma em 
 
a. I, apenas. 
 
b. I, II e III. 
 
c. II, apenas. 
 
d. I e II, apenas. 
 
e. III, apenas. 
0,175 pontos 
PER GUNTA 4 
1. O algoritmo de busca em profundidade sempre analisa os filhos do vértice verificado, o 
que cria uma árvore de 
 
a. retorno. 
 
b. avanço. 
 
c. cruzamento. 
 
d. largura. 
 
e. profundidade. 
 
 
PER GUNTA 1 
1. Um grafo G = (V, A) direcionado é dito fracamente conexo quando 
 
a. existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos 
entre i e j seja menor que 1. 
 
b. não existe, pelo menos, um par de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
 
c. existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja maior que 1. 
 
d. não existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 3. 
 
e. existe, pelo menos, dois pares de vértices i e j em G tal que o número de 
caminhos entre i e j seja menor que 2. 
0,175 pontos 
PER GUNTA 2 
1. É CORRETO afirmar que um grafo é dito planar se 
 
a. admitir uma representação no plano de modo e que exista cruzamento de 
aresta. 
 
b. admitir uma representação no plano, de modo que neste não exista cruzamento 
de aresta. 
 
c. houver conexão em todos os vértices. 
 
d. for um grafo K3,3. 
 
e. admitir representação no plano de modo que exista cruzamento de vértices. 
0,175 pontos 
PER GUNTA 3 
1. O teorema de Kuratowski diz que um grafo G = (V, A) é 
 
a. planar se e somente se G não contém uma subdivisão K3 ou K1,1. 
 
b. planar se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
c. planar se e somente se G não contém uma subdivisão K3 ou K4,4. 
 
d. colorido se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
e. conexo se e somente se G não contém uma subdivisão K5 ou K3,3. 
0,175 pontos 
PER GUNTA 4 
1. Em um grafo G = (V, A) 
 
a. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe 
caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e j 
estão fortemente conectados em um grafo G = (V, A) não direcionado, se 
existem dois caminhos distintos em arestas de i para j em G. 
 
b. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe 
mais de um caminho direcionado de i para j e de j para i em G. Agora, dois 
vértices i e j estão fortemente conectados em um grafo G = (V, A) não 
direcionado, se existe um caminho distinto em arestas de i para j em G. 
 
c. direcionado, é dito que dois vértices i e j estão fortemente conectados, se 
existe, pelo menos, dois caminhos direcionados de i para j e de j para i em G. 
Agora, dois vértices i e j estão fortemente conectados em um grafo G = (V, A) 
não direcionado, se existe um caminho em arestas de i para j em G. 
 
d. não direcionado, é dito que dois vértices i e j estão fortemente conectados, se 
existe caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e 
j estão fortemente conectados em um grafo G = (V, A) direcionado, se existem 
dois caminhos distintos em arestas de i para j em G. 
 
e. não direcionado, é dito que dois vértices i e j estão fortemente conectados, se 
existe n caminhos direcionados de i para j e de j para i em G. Agora, dois 
vértices i e j estão fortemente conectados em um grafo G = (V, A) direcionado, 
se existe um caminho distinto em arestas de i para j em G. 
 
 
PER GUNTA 1 
1. O que são laços? 
 
a. Arestas que ligam um grafo bipartido. 
 
b. Arestas que ligam dois vértices diferentes. 
 
c. Arestas que ligam um grafo simples. 
 
d. Nenhuma das alternativas anteriores. 
 
e. Arestas que ligam um vértice a ele mesmo. 
0,15 pontos 
PER GUNTA 2 
1. Observe o grafo abaixo e assinale a alternativa correta. 
 
 
a. Nenhuma das alternativas anteriores. 
 
b. É um grafo simples. 
 
c. É um grafo buquê. 
 
d. É um grafo bipartido. 
 
e. É um grafo orientado. 
0,15 pontos 
PER GUNTA 3 
1. O que são grafos rotulados? 
 
a. Grafos que possuem rótulos nos vértices ou arestas. 
 
b. Grafos nulos. 
 
c. Grafos triviais. 
 
d. Grafos que possuem arestas paralelas. 
 
e. Grafos que possuem laços. 
0,15 pontos 
PER GUNTA 4 
1. Com relação ao grafo abaixo, ele é: 
 
 
a. Buquê. 
 
b. Trivial. 
 
c. Hipergrafo. 
 
d. Nulo. 
 
e. Vazio. 
 
 
PER GUNTA 1 
1. Leia as afirmações a seguir: 
I. Grafos são compostos por vértices e arestas; 
II. A Teoria dos grafos tem como enfoque principal o estudo da natureza; 
III. O objetivo da teoria dos grafos é estudar o relacionamento entre os objetos; 
IV. Grafos podem se compreendidos como estruturas do mundo real utilizadas na 
natureza. 
Analisando estas informações, é possível afirmar que: 
 
a. Somente as afirmações I e III estão corretas. 
 
b. Somente as afirmações I e II estão corretas. 
 
c. Somente a afirmação I esta correta. 
 
d. Somente as afirmações I e IV estão corretas. 
 
e. Somente as afirmações II e III estão corretas. 
0,15 pontos 
PER GUNTA 2 
1. Segundo o texto, grafos podem ser utilizados em mapas de rodovias? Como? 
 
a. Sim, grafos podem representar a população no mapa. 
 
b. Nenhuma das alternativas anteriores. 
 
c. Sim, grafos podem representar as cidades por arestas, e os vértices podem 
representar as rodovias que ligam as cidades. 
 
d. Sim, grafos podem representar cidades por vértices, e as arestas podem 
representar as rodovias que ligam as cidades. 
 
e. Não, grafos não podem ser utilizados em mapas de rodovias. 
0,15 pontos 
PER GUNTA 3 
1. O desenho a seguir é considerado um grafo? Se sim, quantos vértices e arestas ele 
possui? 
 
 
a. Não, o desenho acima não é um grafo. 
 
b. Sim, o desenho acima é um grafo de 6 vértices e 4 arestas. 
 
c. Sim, o desenho acima é um grafo de 4 vértices e 6 arestas. 
 
d. Sim, o desenho acima é um grafo de 2 vértices e 3 arestas. 
 
e. Sim, o desenho acima é um grafo de 4 vértices e 3 arestas. 
0,15 pontos 
PER GUNTA 4 
1. A teoria dos grafos começou em 1736 com um matemático suíço. Ele propôs uma 
solução para um problema utilizando grafos. Qual foi esse problema? 
 
a. Problema da atmosfera da terra. 
 
b. Problema das sete pontes de Konigsberg. 
 
c. Problema da forma de água. 
 
d. Nenhuma das alternativas anteriores. 
 
e. Problema dos 12 carros. 
 
TEORIA DOS GRAFOS 
 
AS 01 
 
PERGUNTA 1 
1. O desenho a seguir é considerado um grafo? Se sim, quantos vértices e arestas ele possui? 
 
 
a. Sim, o desenho acima é um grafo de 4 vértices e 3 arestas. 
 
b. Não, o desenho acima não é um grafo. 
 
c. Sim, o desenho acima é um grafo de 6 vértices e 4 arestas. 
 
d. Sim, o desenho acima é um grafo de 2 vértices e 3 arestas. 
 
e. Sim, o desenho acima é um grafo de 4 vértices e 6 arestas. 
0,15 pontos 
PERGUNTA 2 
1. Grafos são bastante utilizados para modelar e resolver problemas. Na modelagem de placas 
de circuitos eletrônicos, são utilizados grafos. Assinale a alternativa que explica corretamente 
como os grafos são utilizados nessa modelagem. 
 
a. Uma placa de circuito eletrônica é composta por diversos componentes eletrônicos. 
Correntes elétricas percorrem por tais componentes. Dessa forma, grafos podem ser 
utilizados para representar o percurso das correntes entre os componentes, onde os 
componentes são representados pelos vértices, e as arestas representam a conexão 
entre os componentes. 
 
b. Uma placa de circuito eletrônica é composta por diversos componentes eletrônicos. 
Correntes elétricas percorrem por tais componentes. Dessa forma, grafos podem ser 
utilizados para representar o percurso das correntes entre os componentes, onde os 
componentes são representados pelas arestas, e os vértices representam a conexão 
entre os componentes. 
 
c. Placa de circuito eletrônica não utiliza grafos.d. Uma placa de circuito eletrônica é composta por diversos componentes eletrônicos. 
Correntes elétricas percorrem por tais componentes. Dessa forma, grafos podem ser 
utilizados para representar a utilização de tais placas em objetos eletrônicos. 
 
e. Nenhuma das alternativas anteriores. 
0,15 pontos 
PERGUNTA 3 
1. A teoria dos grafos começou em 1736 com um matemático suíço. Ele propôs uma solução para 
um problema utilizando grafos. Qual foi esse problema? 
 
a. Problema dos 12 carros. 
 
b. Problema das sete pontes de Konigsberg. 
 
c. Problema da forma de água. 
 
d. Nenhuma das alternativas anteriores. 
 
e. Problema da atmosfera da terra. 
0,15 pontos 
PERGUNTA 4 
1. Quem foi o primeiro a propor uma solução utilizando grafos? 
 
a. Albert Einstein. 
 
b. Nikola Tesla. 
 
c. Thomas Edison. 
 
d. Leonhard Euler. 
 
e. Isaac Newton. 
 
 
AS 02 
 
 
PERGUNTA 1 
1. O que são grafos rotulados? 
 
a. Grafos nulos. 
 
b. Grafos que possuem arestas paralelas. 
 
c. Grafos que possuem rótulos nos vértices ou arestas. 
 
d. Grafos que possuem laços. 
 
e. Grafos triviais. 
0,15 pontos 
PERGUNTA 2 
1. O que são grafos ponderados? 
 
a. Grafos nulos. 
 
b. Grafos que possuem pesos associados em suas arestas ou vértices. 
 
c. Grafos que possuem laços. 
 
d. Nenhuma das alternativas anteriores. 
 
e. Grafos que possuem buquê. 
0,15 pontos 
PERGUNTA 3 
1. Com relação ao grafo abaixo, ele é: 
 
 
 
a. Simples. 
 
b. Multigrafo. 
 
c. Bipartido. 
 
d. Pseudografo. 
 
e. Reflexivo. 
0,15 pontos 
PERGUNTA 4 
1. Observe o grafo abaixo e assinale a alternativa correta. 
 
 
a. É um grafo bipartido. 
 
b. É um grafo simples. 
 
c. É um grafo buquê. 
 
d. Nenhuma das alternativas anteriores. 
 
e. É um grafo orientado. 
 
 
 
AS 03 
 
PERGUNTA 1 
1. Um grafo G = (V, A) direcionado é dito fracamente conexo quando 
 
a. não existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos 
entre i e j seja menor que 2. 
 
b. existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos entre 
i e j seja menor que 2. 
 
c. existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos entre 
i e j seja maior que 1. 
 
d. existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos entre i e 
j seja menor que 1. 
 
e. não existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos 
entre i e j seja menor que 3. 
0,175 pontos 
PERGUNTA 2 
1. Coloração harmoniosa é uma coloração onde 
 
a. cada par de cores aparece, no mínimo, em um único vértice adjacente no grafo G. 
 
b. cada par de cores aparece, no máximo, em um par de vértices adjacentes no grafo G. 
 
c. cada par de cores aparece, no mínimo, em um par de vértices adjacentes no grafo G. 
 
d. as cores aparecem, no máximo, em dois pares de vértices adjacentes no grafo G. 
 
e. cada par de cores aparece, no máximo, em dois pares de vértices adjacentes no grafo 
G. 
0,175 pontos 
PERGUNTA 3 
1. Em um grafo G = (V, A) 
 
a. não direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe 
caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e j estão 
fortemente conectados em um grafo G = (V, A) direcionado, se existem dois caminhos 
distintos em arestas de i para j em G. 
 
b. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe mais de 
um caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e j estão 
fortemente conectados em um grafo G = (V, A) não direcionado, se existe um caminho 
distinto em arestas de i para j em G. 
 
c. não direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe n 
caminhos direcionados de i para j e de j para i em G. Agora, dois vértices i e j estão 
fortemente conectados em um grafo G = (V, A) direcionado, se existe um caminho 
distinto em arestas de i para j em G. 
 
d. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe caminho 
direcionado de i para j e de j para i em G. Agora, dois vértices i e j estão fortemente 
conectados em um grafo G = (V, A) não direcionado, se existem dois caminhos distintos 
em arestas de i para j em G. 
 
e. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe, pelo 
menos, dois caminhos direcionados de i para j e de j para i em G. Agora, dois vértices i e 
j estão fortemente conectados em um grafo G = (V, A) não direcionado, se existe um 
caminho em arestas de i para j em G. 
0,175 pontos 
PERGUNTA 4 
1. Um grafo é denominado k-conexo quando para 
 
a. todas as arestas de G existem, pelo menos, K caminhos iguais entre as quais. 
 
b. qualquer par de vértices de G existem, pelo menos, K caminhos diferentes entre os 
quais. 
 
c. qualquer par de vértices de G existem, pelo menos, 3 caminhos iguais entre os quais. 
 
d. todas as arestas de G existem, pelo menos, k-7 caminhos diferentes entre as quais. 
 
e. todos os pares de vértices de G existem, pelo menos, 2 caminhos diferentes entre os 
quais. 
 
AS 04 
 
PERGUNTA 1 
1. Leia atentamente as seguintes afirmações: 
I A ideia central implementada no algoritmo de busca em largura é analisar os vértices vizinhos 
do vértice em verificação. 
II A ideia central implementada no algoritmo de busca em profundidade é analisar os vértices 
filhos do seu vértice pai. 
III Tanto a busca em largura, como a busca em profundidade se baseiam em valores 
conhecidos no percussor. 
É VERDADEIRO o que se afirma em 
 
a. III, apenas. 
 
b. I, II e III. 
 
c. I, apenas. 
 
d. II, apenas. 
 
e. I e II, apenas. 
0,175 pontos 
PERGUNTA 2 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso v seja 
descendente de w, então a aresta será 
 
a. de cruzamento. 
 
b. ponderada. 
 
c. orientada. 
 
d. de avanço.. 
 
e. de retorno. 
0,175 pontos 
PERGUNTA 3 
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso w seja 
descendente de v, então a aresta será 
 
a. de retorno. 
 
b. de cruzamento. 
 
c. orientada. 
 
d. ponderada. 
 
e. de avanço.. 
0,175 pontos 
PERGUNTA 4 
1. Tal como sugere o seu nome, o algoritmo busca em largura utiliza a técnica de busca em 
largura, cujo procedimento sempre 
 
a. busca um caminho alternativo. 
 
b. analisa os filhos e vizinhos do vértice verificado. 
 
c. analisa o vértice final primeiro. 
 
d. analisa os vizinhos do vértice verificado, apenas. 
 
e. analisa os filhos do vértice verificado, apenas. 
 
 
AS 05 
 
PERGUNTA 1 
1. Passeio em grafos consiste de uma sequência 
 
a. finita alternada de caminhos, que começa e termina por vértices. 
 
b. finita alternada de caminhos, que começa e termina por vértices, tal que cada caminho 
começa no vértice inicial e termina no vértice final. 
 
c. infinita de caminhos, que começa e termina por vértices, tal que cada caminho possui, 
no mínimo, um vértice. 
 
d. infinita de caminhos, que começa e termina por vértices, tal que cada caminho possui, 
no mínimo, dois vértices. 
 
e. finita alternada de vértices e arestas, que começa e termina por vértices, tal que cada 
aresta é incidente ao vértice que a precede e ao que a sucede. 
0,175 pontos 
PERGUNTA 2 
1. Um grafo é denominado hamiltoniano quando neste existe um caminho que 
 
a. contém somente o vértice inicial. 
 
b. contém todos os vértices de G. 
 
c. contém somente o vértice final. 
 
d. não passa por nenhum vértice. 
 
e. contém somente os vértices inicial e final. 
0,175 pontos 
PERGUNTA 3 
1. Um grafo é denominado euleriano quando neste existe um ciclo que 
 
a. passa por todas as arestas de G sem repetição. 
 
b. não passa por aresta alguma. 
 
c. passa somente pelo vértice inicial. 
 
d. não passa pelo vértice inicial. 
 
e. passa somente pelo vértice final. 
0,175 pontosPERGUNTA 4 
1. Um caminho mais curto entre dois vértices v e w de um grafo G NÃO ponderado é aquele 
 
a. que acumula a quantidade de três arestas entre v e w. 
 
b. que acumula a menor quantidade de arestas entre v e w. 
 
c. que acumula a quantidade de zero aresta entre v e w. 
 
d. que acumula a maior quantidade de arestas entre v e w. 
 
e. no qual não há caminho entre as arestas v e w. 
 
 
AS 06 
 
PERGUNTA 1 
1. Na teoria de grafos, floresta é um conjunto de 
 
a. árvores sem arestas em comum. 
 
b. arestas com vértices em comum. 
 
c. árvores sem vértices em comum. 
 
d. arestas sem vértices em comum. 
 
e. árvores com vértices em comum. 
0,175 pontos 
PERGUNTA 2 
1. Árvore geradora de um grafo G é um subgrafo gerador 
 
a. conexo e cíclico. 
 
b. desconexo e acíclico. 
 
c. desconexo em vértices e cíclico em arestas. 
 
d. desconexo e cíclico. 
 
e. conexo e acíclico. 
0,175 pontos 
PERGUNTA 3 
1. Fluxo em rede é o 
 
a. ato de não transportar objetos por diversas redes. 
 
b. grafo de tamanho G. 
 
c. mecanismo de não transportar objetos por uma rede. 
 
d. ato de transportar objetos por uma rede. 
 
e. ato de não transportar objetos por uma rede. 
0,175 pontos 
PERGUNTA 4 
1. Leia atentamente as seguintes afirmações: 
I Floresta é um conjunto de árvores sem vértice em comum. 
II Floresta geradora contém todos os vértices de G. 
III Floresta geradora é um grafo que generaliza o conceito de árvore geradora. 
É VERDADEIRO o que se afirma em 
 
a. I e II, apenas. 
 
b. II, apenas. 
 
c. I, apenas. 
 
d. III, apenas. 
 
e. II e III, apenas. 
 
 
 
AS3 GRAFOS 
E C A C 
 
PERGUNTA 1 
1. O teorema de Kuratowski diz que um grafo G = (V, A) é 
 
a. conexo se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
b. planar se e somente se G não contém uma subdivisão K3 ou K4,4. 
 
c. planar se e somente se G não contém uma subdivisão K3 ou K1,1. 
 
d. colorido se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
e. planar se e somente se G não contém uma subdivisão K5 ou K3,3. 
0,175 pontos 
PERGUNTA 2 
1. Um grafo é denominado k-conexo quando para 
 
a. todas as arestas de G existem, pelo menos, K caminhos iguais entre as quais. 
 
b. todos os pares de vértices de G existem, pelo menos, 2 caminhos diferentes 
entre os quais. 
 
c. qualquer par de vértices de G existem, pelo menos, K caminhos diferentes entre 
os quais. 
 
d. todas as arestas de G existem, pelo menos, k-7 caminhos diferentes entre as 
quais. 
 
e. qualquer par de vértices de G existem, pelo menos, 3 caminhos iguais entre os 
quais. 
0,175 pontos 
PERGUNTA 3 
1. É CORRETO afirmar que um grafo é dito planar se 
 
a. admitir uma representação no plano, de modo que neste não exista cruzamento 
de aresta. 
 
b. admitir uma representação no plano de modo e que exista cruzamento de 
aresta. 
 
c. for um grafo K3,3. 
 
d. houver conexão em todos os vértices. 
 
e. admitir representação no plano de modo que exista cruzamento de vértices. 
0,175 pontos 
PERGUNTA 4 
1. Em um grafo G = (V, A) 
 
a. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe, 
pelo menos, dois caminhos direcionados de i para j e de j para i em G. Agora, 
dois vértices i e j estão fortemente conectados em um grafo G = (V, A) não 
direcionado, se existe um caminho em arestas de i para j em G. 
 
b. não direcionado, é dito que dois vértices i e j estão fortemente conectados, se 
existe n caminhos direcionados de i para j e de j para i em G. Agora, dois 
vértices i e j estão fortemente conectados em um grafo G = (V, A) direcionado, 
se existe um caminho distinto em arestas de i para j em G. 
 
c. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe 
caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e j 
estão fortemente conectados em um grafo G = (V, A) não direcionado, se 
existem dois caminhos distintos em arestas de i para j em G. 
 
d. não direcionado, é dito que dois vértices i e j estão fortemente conectados, se 
existe caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e 
j estão fortemente conectados em um grafo G = (V, A) direcionado, se existem 
dois caminhos distintos em arestas de i para j em G. 
 
e. direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe 
mais de um caminho direcionado de i para j e de j para i em G. Agora, dois 
vértices i e j estão fortemente conectados em um grafo G = (V, A) não 
direcionado, se existe um caminho distinto em arestas de i para j em G. 
0,175 pontos 
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para 
salvar todas as respostas. 
 
Teoria dos Grafos 
AS I 
PERGUNTA 1 
1. Quem foi o primeiro a propor uma solução utilizando grafos? 
 
a. Isaac Newton. 
 
b. Thomas Edison. 
 
c. Leonhard Euler. 
 
d. Albert Einstein. 
 
e. Nikola Tesla. 
0,15 pontos 
PERGUNTA 2 
1. Leia as afirmações a seguir: 
I. Grafos são compostos por vértices e arestas; 
II. A Teoria dos grafos tem como enfoque principal o estudo da natureza; 
III. O objetivo da teoria dos grafos é estudar o relacionamento entre os objetos; 
IV. Grafos podem se compreendidos como estruturas do mundo real utilizadas na 
natureza. 
Analisando estas informações, é possível afirmar que: 
 
a. Somente a afirmação I esta correta. 
 
b. Somente as afirmações II e III estão corretas. 
 
c. Somente as afirmações I e IV estão corretas. 
 
d. Somente as afirmações I e III estão corretas. 
 
e. Somente as afirmações I e II estão corretas. 
0,15 pontos 
PERGUNTA 3 
1. Grafos são bastante utilizados para modelar e resolver problemas. Na modelagem de 
placas de circuitos eletrônicos, são utilizados grafos. Assinale a alternativa que explica 
corretamente como os grafos são utilizados nessa modelagem. 
 
a. Uma placa de circuito eletrônica é composta por diversos componentes 
eletrônicos. Correntes elétricas percorrem por tais componentes. Dessa forma, 
grafos podem ser utilizados para representar a utilização de tais placas em 
objetos eletrônicos. 
 
b. Uma placa de circuito eletrônica é composta por diversos componentes 
eletrônicos. Correntes elétricas percorrem por tais componentes. Dessa forma, 
grafos podem ser utilizados para representar o percurso das correntes entre os 
componentes, onde os componentes são representados pelas arestas, e os 
vértices representam a conexão entre os componentes. 
 
c. Placa de circuito eletrônica não utiliza grafos. 
 
d. Uma placa de circuito eletrônica é composta por diversos componentes 
eletrônicos. Correntes elétricas percorrem por tais componentes. Dessa forma, 
grafos podem ser utilizados para representar o percurso das correntes entre os 
componentes, onde os componentes são representados pelos vértices, e as 
arestas representam a conexão entre os componentes. 
 
e. Nenhuma das alternativas anteriores. 
0,15 pontos 
PERGUNTA 4 
1. O desenho a seguir é considerado um grafo? Se sim, quantos vértices e arestas ele 
possui? 
 
 
a. Sim, o desenho acima é um grafo de 4 vértices e 6 arestas. 
 
b. Sim, o desenho acima é um grafo de 6 vértices e 4 arestas. 
 
c. Sim, o desenho acima é um grafo de 4 vértices e 3 arestas. 
 
d. Não, o desenho acima não é um grafo. 
 
e. Sim, o desenho acima é um grafo de 2 vértices e 3 arestas. 
 
 
 
AS II 
 
 
PERGUNTA 1 
1. O que são grafos rotulados? 
 
a. Grafos triviais. 
 
b. Grafos que possuem rótulos nos vértices ou arestas. 
 
c. Grafos que possuem arestas paralelas. 
 
d. Grafos nulos. 
 
e. Grafos que possuem laços. 
0,15 pontos 
PERGUNTA 2 
1. O que são grafos ponderados? 
 
a. Grafos nulos. 
 
b. Grafos que possuem laços. 
 
c. Grafos que possuem pesos associados em suas arestas ou vértices. 
 
d. Nenhuma das alternativas anteriores. 
 
e. Grafos que possuem buquê. 
0,15 pontos 
PERGUNTA 3