Exercício 3 · Exame Nacional Matemática Aplicada às Ciências Sociais 1.ª fase 2022

Tema: Grafos e algoritmos · Do exame 1.ª fase (2022)

Enunciado

Na agência de viagens Ir&Voltar, realizam-se, ao longo da primeira segunda-feira de cada trimestre, seis reuniões de trabalho, R 1, R 2, R 3, R 4, R 5 e R 6. Cada reunião tem um tema diferente e dura 90 minutos. De modo a planificar o dia das reuniões, é solicitada a cada funcionário a inscrição em uma ou mais reuniões, de acordo com os seus interesses. Para que todos os funcionários possam assistir às reuniões em que se inscrevem, é criado um horário com blocos de reuniões que possam ocorrer em simultâneo.

Na Tabela 2, apresentam-se as inscrições dos funcionários em cada uma das reuniões a realizar na primeira segunda-feira do terceiro trimestre de 2022.

Tabela 2

R 1

R 2

R 3

R 4

R 5

R 6

António

Bernardo

Diamantino

Ana

Célia

Bernardo

Diamantino

Fausto

Elsa

Guilherme

Elsa

Célia

Elsa

Guilherme

Fausto

Ilda

Guilherme

Zulmira

Xavier

Paulo

Xavier

Tomás

Com o propósito de determinar o tempo mínimo necessário para que as seis reuniões decorram nas condições definidas, a diretora de planeamento da Ir&Voltar começou por construir um grafo que modelava a situação.

Indique, em horas, o tempo mínimo necessário para que as seis reuniões se realizem nas condições definidas.

Na sua resposta:

apresente um grafo que a diretora de planeamento pudesse ter construído;

identifique a constituição de cada bloco de reuniões.

Enunciado: Exercício 3 · Exame Nacional Matemática Aplicada às Ciências Sociais 1.ª fase 2022

Resolução

Segundo os critérios oficiais de classificação

Apresente um grafo que a diretora de planeamento pudesse ter construído

Resposta: Grafo com 6 vértices ( $R1, R2, R3, R4, R5, R6$ ). Se as arestas representarem incompatibilidade (partilha de funcionários): - $R1$ liga com $R2$ (António), $R3$ (Bernardo) e $R6$ (Célia); - $R2$ liga com $R1$ , $R4$ (Diamantino, Elsa), $R5$ (Xavier) e $R6$ (Elsa); - $R3$ liga com $R1$ , $R4$ (Fausto, Paulo), $R5$ (Guilherme) e $R6$ (Guilherme); - $R4$ liga com $R2$ , $R3$ e $R6$ (Elsa); - $R5$ liga com $R2$ , $R3$ e $R6$ (Guilherme); - $R6$ liga com $R1$ , $R2$ , $R3$ , $R4$ e $R5$ . Alternativamente, as arestas podem representar a possibilidade de realização em simultâneo (grafo complementar).

Identifique a constituição de cada bloco de reuniões

Resposta: Três blocos de reuniões: um bloco com $R1$ , $R4$ e $R5$ ; um bloco com $R2$ e $R3$ ; e um bloco com $R6$ sozinho. (Ou seja: [ $R1, R4$ e $R5$ ; $R2$ e $R3$ ; $R6$ ]).

Indique, em horas, o tempo mínimo necessário para que as seis reuniões se realizem nas condições definidas

Resposta: $4{,}5$ h / $4.5$ h

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 3 · 2.ª fase 2023 · Exercício 3 · 2.ª fase 2022 ›

Mais exercícios de Grafos e algoritmos

O exame completo · 1.ª fase (2022)