AV1 AV2 AV3
1ª ch
2ª ch
Curso: Disciplina: Código/Turma:
Professor/a: Data:
Aluno/a: Matrícula:
INSTRUÇÕES GERAIS PARA A AVALIAÇÃO
● A prova possui duração de 1h40min e vale 7,0 pontos;
● Os únicos softwares LIBERADOS para desenvolvimento da prova, são o Visual Studio
Code, IntelliJ e o Adobe Acrobat Reader.
● A prova é com consulta ao material didático da disciplina e repositórios dos algoritmos em
Java e Python disponibilizados numa pasta na rede do laboratório.
● O acesso à internet durante a prova será RESTRITO apenas aos alunos que terminarem a
prova para envio das respostas ao AVA. Esta solicitação é individual e monitorada!
● O padrão de envio de resposta é o número da questão e as alternativas verdadeiras
separadas por um espaço. Por exemplo, 1 A B C refere-se à questão 1 com alternativas
verdadeiras A, B e C. Formato do arquivo será txt.
● Quaisquer tipos de dispositivos eletrônicos de uso pessoal devem permanecer
DESLIGADOS na mochila, ou na mesa do professor durante toda a prova;
● Tentativas de fraude ou cola implicará em nota zero para todas as pessoas envolvidas
QUESTÃO 1 (0,5 ponto)
Considere um grafo G com 15 vértices e 4 componentes conexos. Avalie as afirmações a seguir:
A. Se todos os 4 componentes tivessem no máximo 3 vértices, o número total de vértices
seria no máximo 12. Portanto, pelo menos um componente tem 4 ou mais vértices.
B. É possível que todos os componentes tenham exatamente o mesmo número de vértices.
C. Para maximizar o tamanho de um componente, basta minimizar o número de vértices nos
outros três. Assim, o maior componente pode ter até 12 vértices.
D. A menor quantidade possível de vértices em um componente conexo é 2, pois é
necessário pelo menos uma aresta.
E. Um grafo com 4 componentes conexos e 15 vértices pode ter um componente com
exatamente 14 vértices.
QUESTÃO 2 (0,5 ponto)
Analise as afirmações a seguir com base nas definições de raio, diâmetro e suas propriedades em
grafos simples e conexos.
A. Em qualquer grafo conectado, o raio é sempre menor ou igual ao diâmetro.
B. Se o raio de um grafo conectado é 3, então seu diâmetro pode ser no máximo 6.
C. Se o diâmetro de um grafo é 1, então o grafo é completo.
D. Existem grafos simples com diâmetro 1 que não são completos, desde que contenham
pelo menos uma aresta entre cada par de vértices.
E. Para todo grafo conectado G, vale a desigualdade raio(G) ≤ diâmetro(G) ≤ 2 raio(G).
QUESTÃO 3 (0,5 ponto)
Para os grafos (a) a (f), assinale as alternativas corretas quanto à classificação dos exemplos
como passeio, trilha ou caminho.
Figura 1: Grafos (a) a (f) da questão 1.
A. No grafo (a), a sequência v1 - v3 - v5 - v6 - v1 é um passeio, mas não uma trilha, pois há
repetição de vértices e potencialmente de arestas.
B. No grafo (b), a sequência v3 - v8 - v5 - v3 não pode ser considerada um passeio, pois há
vértices repetidos.
C. No grafo (c), a sequência v1 - v4 - v7 - v6 é corretamente classificada como trilha e
também como caminho.
D. No grafo (e), a sequência v1 - v2 - v3 - v9 - v7 é uma trilha, pois nenhuma aresta se repete,
e todos os vértices são distintos.
E. No grafo (f), a sequência v2 - v1 - v3 - v5 - v6 é um passeio válido, mas não é uma trilha
pois repete a aresta entre v3 e v5.
2
QUESTÃO 4 (0,5 ponto)
Considere um grafo conectado G e uma aresta e = {u, v} pertencente a um ciclo. Avalie as
afirmações a seguir.
A. A remoção de uma aresta qualquer de um grafo conectado sempre resulta em um grafo
ainda conectado.
B. Se uma aresta pertence a um ciclo, então existe outro caminho entre seus extremos que
não utiliza essa aresta.
C. A remoção de uma aresta que pertence a um ciclo não desconecta o grafo.
D. D Se uma aresta pertence a um ciclo, então é a única conexão possível entre dois vértices.
E. Para garantir que G - e seja conexo, é suficiente que $e$ pertença a um ciclo.
QUESTÃO 5 (0,5 ponto)
Considere o seguinte teorema: "Todo grafo simples e conectado com n vértices possui pelo menos
n - 1 arestas". Avalie as afirmações abaixo com base nessa proposição.
A. Um grafo com apenas um vértice e sem arestas já é considerado conectado.
B. O número mínimo de arestas em um grafo simples e conectado com n vértices é
exatamente n - 1, independentemente da estrutura do grafo.
C. Em qualquer passo da indução, é possível remover um vértice sem afetar a conectividade
do grafo resultante.
D. Se um grafo simples tem menos de n - 1 arestas, ele necessariamente é desconectado.
E. A adição de arestas além de n - 1 pode manter o grafo conectado, mas não é necessária
para garantir sua conectividade mínima.
QUESTÃO 6 (0,5 ponto)
Analise os grafos apresentados e identifique, entre as alternativas abaixo, quais afirmam
corretamente se os grafos são ou não hamiltonianos.
Figura 2: Grafos de (a) a (d) da questão 6.
A. O grafo (a) é hamiltoniano, pois contém um ciclo que visita todos os vértices uma única vez
antes de retornar ao início.
B. O grafo (b) é hamiltoniano, pois, apesar da sobreposição visual das arestas, existe um
ciclo que percorre todos os vértices.
C. O grafo (c) é hamiltoniano, uma vez que possui um grau mínimo 3 e estrutura cíclica
fechada com 8 vértices conectados.
D. O grafo (d) não é hamiltoniano, pois há vértices periféricos (como g e a) que tornam
impossível formar um único ciclo que visite todos os vértices exatamente uma vez.
E. Um grafo com todos os vértices de grau 2 ou mais é sempre hamiltoniano.
3
QUESTÃO 7 (0,5 ponto)
Nos dois grafos apresentados, deseja-se encontrar o menor circuito fechado que percorra todas
as arestas ao menos uma vez, conforme o Problema do Carteiro Chinês. Qual das alternativas
descreve corretamente os custos mínimos desses percursos?
Figura 3: Grafos (a) e (b), respectivamente superior e inferior, da questão 7.
A. O grafo superior tem custo 44 e o grafo inferior tem custo 103.
B. O grafo superior tem custo 37 e o grafo inferior tem custo 103.
C. O grafo superior tem custo 44 e o grafo inferior tem custo 85.
D. O grafo superior tem custo 45 e o grafo inferior tem custo 103.
E. Ambos os grafos possuem custos maiores que 100.
QUESTÃO 8 (0,5 ponto)
Considere o grafo abaixo, onde os vértices representam cidades e os pesos das arestas
representam o custo de deslocamento entre elas. Sabendo que o ponto de partida e de chegada
deve ser o vértice e, selecione as afirmativas corretas sobre possíveis soluções do problema do
caixeiro-viajante nesse grafo.
Figura 4: Grafo da questão 8.
A. O ciclo {e → b → a → c → d → e} é uma solução válida e possui custo total 23.
B. O ciclo {e → c → a → b → d → e} é o de menor custo entre todos os que iniciam em e.
4
C. O ciclo {e → d → c → a → b → e} é uma solução ótima.
D. Qualquer ciclo que visite todos os vértices apenas uma vez e retorne ao vértice e é
automaticamente a solução de menor custo.
E. Existem dois ciclos distintos com custo mínimo de 23 que resolvem o problema do
caixeiro-viajante com início e fim em e.
QUESTÃO 9 (0,5 ponto)
Uma firma precisa armazenar sete produtos químicos diferentes (Q1 a Q7), sendo que certos
pares não podem ser colocados juntos no mesmo local por segurança. A tabela de restrições foi
convertida em um grafo simples onde há uma aresta entre dois produtos se não podem ser
armazenados juntos. Utilizando um algoritmo de coloração de vértices, determine o número
mínimo de locais (cores) necessários e quais produtos podem ser armazenados juntos.
Q1 Q2 Q3 Q4 Q5 Q6 Q7
Q1 * * * *
Q2 * * * *
Q3 * * * *
Q4 * * * * *
Q5 * * * * *
Q6 * * * * *
Q7 * * * *
Tabela 1: Tabela de restrições da questão 9.
A. São necessários 4 locais distintos, com a seguinte alocação: Local 1 — Q1, Q3; Local 2 —
Q2, Q5; Local 3 — Q4, Q7; Local 4 — Q6.
B. O número mínimo de locais necessários é 3, pois é possível colorir o grafo com três cores
sem conflitos.
C. O produto Q6 exige uma cor própria, pois é adjacente a produtos com as três cores já
utilizadas.
D. A coloração ótima pode ser obtida com uma abordagem gulosa, respeitando os graus dos
vértices.
E. Produtos Q4 e Q5 podem ser armazenados juntos, pois não são adjacentes no grafo de
restrições.
5
QUESTÃO 10 (0,5 ponto)
No grafo euleriano da figura, qual das alternativas descreve corretamente as diferenças nos
**resultados** obtidos ao aplicar os algoritmos de Hierholzer e Fleury a partir do vértice $d$?
Figura 4: Grafo da questão 10.
A. Hierholzer gera um ciclo euleriano passando pelo vértice g antes de visitar os vértices h, i e
j; já Fleury visita h, i e j antes de f.
B. Ambos produzem o mesmo ciclo euleriano, mas com a ordem dos vértices invertida.
C. O algoritmo de Hierholzer passa por todos os vértices duas vezes, enquanto o de Fleury
passa por todos apenas uma vez.
D. O ciclo gerado por Fleury evita o vértice g até o fim do percurso, enquanto Hierholzer o
visita logo após o vértice e.
E. Fleury evita utilizar pontes no início, o que muda a ordem de visita em relação ao ciclo
obtido por Hierholzer.
QUESTÃO 11 (0,5 ponto)
O grafo do cavalo 3×3 é construído com base nas 9 posições de um tabuleiro 3×3, onde cada
posição é um vértice, e há uma aresta entre duas posições se o cavalo pode se mover de uma
para a outra com um movimento em "L". Com base nessa definição, analise as afirmativas a
seguir.
Figura 5: Grafo do cavalo 8x8.
A. O vértice central (2,2) é isolado, pois o cavalo não pode sair nem chegar a essa posição no
tabuleiro 3×3.
B. Todos os vértices do grafo estão em um mesmo componente conexo.
C. O grafo possui exatamente dois componentes conexos.
D. Os vértices (1,1) e (3,3) pertencem ao mesmo componente conexo.
E. O vértice (2,2) possui grau 1, pois tem apenas um vizinho possível.
6
QUESTÃO 12 (0,5 ponto)
Considere o grafo direcionado acíclico (DAG) formado pelas seguintes arestas: 3-7, 1-4, 7-8, 0-5,
5-2, 3-8, 2-9, 0-6, 4-9, 2-6, 6-4. Com base na aplicação do algoritmo de ordenação topológica por
busca em profundidade (DFS) com uso da pós-ordem reversa, avalie as afirmações abaixo.
A. O vértice 3 aparece antes de 7 e 8 na ordenação topológica.
B. O vértice 1 aparece depois do vértice 4 na ordenação topológica.
C. A sequência {3, 7, 8, 1, 0, 5, 2, 6, 4, 9} é uma ordenação topológica válida para o grafo.
D. O vértice 0 aparece depois de 5 e 2 na ordenação topológica.
E. O vértice 9 deve ser o último vértice na ordenação, pois não possui arestas de saída.
QUESTÃO 13 (0,5 ponto)
Considere as afirmações abaixo e assinale as alternativas corretas.
A. Em um DAG, cada vértice forma seu próprio componente fortemente conexo.
B. A pós-ordem reversa de um grafo direcionado é igual à pós-ordem de seu reverso.
C. Inverter as etapas do algoritmo de Kosaraju-Sharir (primeira DFS em G, segunda em G^R)
ainda produz os componentes corretos.
D. Utilizar BFS em vez de DFS na segunda etapa do algoritmo de Kosaraju-Sharir pode
identificar corretamente os componentes fortemente conexos.
E. O algoritmo de Kosaraju-Sharir não pode ser aplicado a grafos com componentes
unitários.
QUESTÃO 14 (0,5 ponto)
Qual(is) das alternativas descreve(m) corretamente propriedades do fecho transitivo do grafo (b)
gerado por (a)?
Figura 6: (a) Grafo e (b) grafo do fecho transitivo de (a).
A. O vértice 1 tem caminho direto ou indireto até os vértices 4 e 5.
B. O vértice 2 alcança todos os outros vértices, inclusive ele mesmo.
C. O vértice 3 possui caminho até o vértice 1, mesmo que esse caminho não seja direto.
D. O vértice 4 não possui nenhum caminho para o vértice 3 no fecho transitivo.
E. O vértice 5 é inalcançável por qualquer vértice, inclusive no fecho transitivo.
FIM DA AVALIAÇÃO
