Grafos: vértices, arestas e menor caminho

Computação, 7º ano: Grafos: vértices, arestas e menor caminho

1. O grafo abaixo representa ruas de um bairro. Os vértices são lugares, e as arestas são ruas que os ligam, com o tempo de caminhada em minutos.

   Aresta (ligação)	Tempo (min)
   Escola – Praça	5
   Escola – Mercado	8
   Praça – Mercado	2
   Praça – Biblioteca	7
   Mercado – Posto de saúde	6
   Biblioteca – Posto de saúde	3

   Quantos vértices e quantas arestas tem esse grafo?

   1. a5 vértices e 6 arestas
   2. b6 vértices e 5 arestas
   3. c5 vértices e 5 arestas
   4. d6 vértices e 6 arestas

2. Use o texto da questão 1.

   Qual é o grau do vértice Praça, isto é, quantas arestas chegam a ele?

   1. a2
   2. b4
   3. c3
   4. d5

3. Use o texto da questão 1.

   Qual é o caminho mais rápido da Escola até o Posto de saúde?

   1. aEscola → Mercado → Posto de saúde (14 minutos)
   2. bEscola → Praça → Mercado → Posto de saúde (13 minutos)
   3. cEscola → Praça → Biblioteca → Posto de saúde (15 minutos)
   4. dEscola → Mercado → Praça → Biblioteca → Posto de saúde (20 minutos)

4. Use o texto da questão 1.

   Um ciclo é um caminho que começa e termina no mesmo vértice, sem repetir arestas. Qual sequência forma um ciclo?

   1. aEscola → Praça → Biblioteca
   2. bPraça → Mercado → Posto de saúde
   3. cEscola → Mercado → Posto de saúde → Biblioteca
   4. dEscola → Praça → Mercado → Escola

5. Use o texto da questão 1.

   Quais vértices têm grau 3?

   1. aEscola e Biblioteca
   2. bSomente a Praça
   3. cBiblioteca e Posto de saúde
   4. dPraça e Mercado

6. Use o texto da questão 1.

   Somando os graus de todos os vértices desse grafo, qual é o resultado?

   1. a6
   2. b5
   3. c12
   4. d10

7. Em um grafo que representa as amizades de uma turma em uma rede social, o que representa cada aresta?

   1. aUma pessoa da turma.
   2. bA amizade entre duas pessoas.
   3. cA quantidade de fotos publicadas.
   4. dO nome da rede social.

8. Ana criou um procedimento menor_caminho(origem, destino) para calcular a rota da Escola até o Posto de saúde. Agora precisa da rota da Biblioteca até o Mercado. O que ela deve fazer?

   1. aReutilizar o procedimento, trocando a origem e o destino.
   2. bEscrever um procedimento totalmente novo para cada par de lugares.
   3. cApagar o procedimento antigo, porque ele só funciona para a Escola.
   4. dCalcular sempre à mão, porque procedimentos não podem ser reutilizados.

9. Em qual situação um grafo é um bom modelo para resolver o problema?

   1. aCalcular a média das notas de um aluno.
   2. bGuardar o texto de uma redação.
   3. cRepresentar as linhas de ônibus que ligam cidades.
   4. dOrdenar os nomes de todos os alunos da turma em ordem alfabética.

10. Desenhe um grafo com quatro ou cinco lugares do caminho entre a sua casa e a escola (por exemplo: casa, padaria, ponto de ônibus, praça, escola). Indique nas arestas o tempo estimado, em minutos, e encontre o caminho mais rápido. Diga também qual vértice tem o maior grau.

ProvaPiloto · provapiloto.com.br