Exercício 4 · Exame Nacional Matemática Aplicada às Ciências Sociais Época especial 2021

Tema: Grafos e algoritmos · Do exame Época especial (2021)

Enunciado

4. De modo a garantir o isolamento acústico entre os diferentes espaços onde funciona a rádio OnOfff, cada uma das portas de ligação irá ser calafetada.

Na Figura 1, apresenta-se uma planta em que estão representados os diferentes espaços onde funciona a rádio OnOfff: um pátio, uma receção e seis salas (S1, S2, S3, S4, S5 e S6).

O responsável pela calafetagem das portas pretende definir um percurso com início e fim no pátio, cruzando todas as portas e entrando em todos os espaços, sem cruzar nenhuma porta mais de uma vez.

Justifique se é possível definir um percurso nas condições indicadas.

Na sua resposta, apresente um grafo que modele a situação descrita.

a)

Apresente um grafo que modele a situação descrita:

b)

Justifique se é possível definir o percurso pretendido:

Enunciado: Exercício 4 · Exame Nacional Matemática Aplicada às Ciências Sociais Época especial 2021

Resolução

Segundo os critérios oficiais de classificação

Apresentar um grafo que modele a situação descrita

Resposta: Grafo conexo com 8 vértices correspondentes aos 8 espaços (Pátio, Receção, S1, S2, S3, S4, S5, S6) e arestas representando as portas de ligação entre eles: - Pátio ligado a: Receção (2 portas), S1 (1 porta), S5 (2 portas), S6 (1 porta); - Receção ligada a: Pátio (2 portas), S1 (1 porta), S2 (1 porta); - S1 ligado a: Pátio (1 porta), Receção (1 porta), S3 (1 porta), S4 (1 porta); - S2 ligado a: Receção (1 porta), S4 (1 porta), S6 (1 porta); - S3 ligado a: S1 (1 porta), S5 (1 porta); - S4 ligado a: S1 (1 porta), S2 (1 porta), S5 (1 porta); - S5 ligado a: Pátio (2 portas), S3 (1 porta), S4 (1 porta), S6 (1 porta); - S6 ligado a: Pátio (1 porta), S2 (1 porta), S5 (1 porta).

Justifique se é possível definir um percurso nas condições indicadas.

Resposta: Não é possível definir o percurso pretendido.

A explicação passo a passo é Premium. Premium

Resolve-o aqui mesmo: correção automática, pistas e solução passo a passo.

‹ Exercício 4 · 2.ª fase 2021

Mais exercícios de Grafos e algoritmos

O exame completo · Época especial (2021)