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

3. Com o intuito de avaliar as condições de segurança de alguns estádios de futebol, uma comissão vai proceder à sua inspeção.

Na Tabela 4, para cada um dos sete estádios passíveis de inspeção, estão indicados o país onde o estádio se localiza e a sua capacidade.

Tabela 4 País onde o estádio se localiza · Capacidade do estádio

África do Sul · 94 736

Austrália · 83 500

Coreia do Norte · 114 000

Espanha · 99 354

França · 81 338

Inglaterra · 90 000

México · 87 000

A comissão decidiu inspecionar apenas os estádios com capacidade superior a 85 000 espectadores.

De modo a definir um percurso, considerou a duração do voo entre os diferentes países que se apresentam na Tabela 5.

Tabela 5 · Austrália · Coreia do Norte · Espanha · França · México · Inglaterra

África do Sul · 14h13 · 15h57 · 10h25 · 11h22 · 18h38 · 11h46

Austrália · · 11h50 · 21h52 · 21h35 · 16h38 · 21h38

Coreia do Norte · · · 12h12 · 11h24 · 15h26 · 11h16

Espanha · · · · 1h32 · 12h18 · 1h55

França · · · · · 11h56 · 5h24

México · · · · · · 11h36

O percurso será definido atendendo ao método seguinte:

escolher o menor tempo de voo, qualquer que ele seja;

escolher, sucessivamente, os menores tempos de voo, garantindo que não são selecionados mais de dois voos que partam do mesmo país ou que cheguem ao mesmo país, e terminar depois de serem selecionados todos os países onde se localizam os estádios a inspecionar.

Apresente o percurso a efetuar pela comissão, com início na África do Sul.

Na sua resposta, apresente:

um grafo que resulte da aplicação do algoritmo descrito;

a ordem pela qual a comissão visitará os estádios.