— Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
— Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta começar a circular. Para planejar, a equipe anotou as ligações entre pontos do bairro, pensando em cada ponto como um “nó” e cada rua como uma “ligação”. As ruas registradas foram: Feira–Terminal, Terminal–Biblioteca, Biblioteca–Parque, Parque–Feira, Biblioteca–Unidade de saúde, Unidade de saúde–Terminal, Parque–Mirante, Mirante–Feira e Terminal–Parque. O percurso precisa usar cada rua exatamente uma vez (sem voltar pela mesma rua). Por organização do mutirão, o triciclo deve terminar na Biblioteca, onde os sacos são pesados antes de seguir para o caminhão. Com base nas ligações do texto, identifique em qual ponto o triciclo deve iniciar para conseguir usar cada rua exatamente uma vez e terminar na Biblioteca.
- A) Iniciar no Parque.
- B) Iniciar no Mirante.
- C) Iniciar no Terminal.
- D) Iniciar na Feira.
- E) Iniciar na Unidade de saúde.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Modele o problema como grafo. Nós: Feira, Terminal, Biblioteca, Parque, Unidade de saúde e Mirante. Ligações: Feira–Terminal, Terminal–Biblioteca, Biblioteca–Parque, Parque–Feira, Biblioteca–Unidade de saúde, Unidade de saúde–Terminal, Parque–Mirante, Mirante–Feira e Terminal–Parque, totalizando 9 ruas. Passo 2: Conte quantas ruas chegam a cada ponto (grau). Feira: 3 (Terminal, Parque, Mirante). Terminal: 4 (Feira, Biblioteca, Unidade de saúde, Parque). Biblioteca: 3 (Terminal, Parque, Unidade de saúde). Parque: 4 (Biblioteca, Feira, Mirante, Terminal). Unidade de saúde: 2. Mirante: 2. Passo 3: Um percurso que usa cada rua exatamente uma vez só é possível se houver no máximo 2 pontos com número ímpar de ligações. Aqui há exatamente 2 pontos ímpares, Feira e Biblioteca, então o percurso existe e deve começar em um deles e terminar no outro. Passo 4: Como o triciclo deve terminar na Biblioteca, ele deve começar na Feira. Passo 5: Confira com um percurso concreto: Feira–Mirante, Mirante–Parque, Parque–Terminal, Terminal–Feira, Feira–Parque, Parque–Biblioteca, Biblioteca–Unidade de saúde, Unidade de saúde–Terminal, Terminal–Biblioteca. São 9 ruas, todas usadas uma vez, terminando na Biblioteca. Passo 6: Por que as outras estão erradas. Parque tem grau par, então o percurso que sai dele deveria terminar nele, não na Biblioteca. Mirante também tem grau par e não é ponto de início possível para terminar na Biblioteca. Terminal tem grau par (4), o mesmo problema do Parque. Unidade de saúde tem grau par (2), então não serve como início de um percurso que termine na Biblioteca. Passo 7: Conclusão: o triciclo deve iniciar na Feira, alternativa D, que coincide com o gabarito oficial.
💡 Dica: Analise os graus dos nós para identificar o ponto inicial do percurso.
Alternativa por alternativa
O aluno acredita que o ponto de partida pode ser qualquer ponto com muitas ligações, e como o Parque tem 4 ruas, supõe que ele seja o ponto ideal para começar. Não percebe que pontos de grau par funcionam como início e fim do mesmo percurso.
O aluno supõe que o Mirante, por estar em um caminho tranquilo entre Parque e Feira, seja um bom ponto de partida. Não verifica a regra dos graus ímpares que define onde o percurso começa e termina.
Por que engana: Confundir o ponto inicial com o ponto final ou não considerar o grau dos nós para o caminho Euleriano.
O aluno pensa que o Terminal, por ser o ponto mais conectado do mapa, deve ser o início. Confunde a ideia de ponto central com a de ponto de início do percurso, sem checar o número de ruas que chegam a cada nó.
Para usar cada rua uma vez, só dois pontos podem ter número ímpar de ruas ligadas. Biblioteca é ímpar; o outro ponto ímpar é a Feira, que deve ser o início.
O aluno escolhe a Unidade de saúde por ser o ponto ligado diretamente à Biblioteca e a dois pontos apenas, achando que um ponto pouco conectado é o início natural. Não observa que ela tem grau par e não forma o percurso exigido.
Raio-X da questão
Caminho Euleriano em grafos
avaliacao
Conceitos básicos de grafos · Noções de grau de vértice
Estude propriedades de grafos e caminhos Eulerianos.
Confundir o ponto inicial com o ponto final ou não considerar o grau dos nós para o caminho Euleriano.
pensamento_critico
cotidiano
Questões parecidas com resolução
- Moradores acompanham a criação de um aplicativo para orientar deslocamentos durante a feira do bairro. No mapa…
- No balcão da biblioteca do bairro, Lia brinca com um carrinho-robô que anda sozinho quando alguém aperta o botão “vai”…
- — Se uma via ficar bloqueada, ainda precisamos orientar os moradores até o abrigo mais próximo — explicou a técnica da…
- "Se um corredor ficar bloqueado, a gente precisa ter uma volta sem se perder", explicou a monitora de um parque ao…
- No fim da tarde, a cozinha solidária do bairro recebe pedidos por mensagem e imprime um bilhete para cada entrega. O…
- Uma equipe de estudantes está modelando, como um grafo dirigido, as conexões entre estações de bicicletas de uma cidade…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog