The Health Department of the imaginary region Scarlet is preparing contingency plans for a potential pandemic. To ensure efficient allocation of resources, they want to determine:
-
Which city would serve as the most effective distribution center for medication, guaranteeing accessibility to the largest number of other cities in the shortest time.
-
Which city would serve as the most strategic location for establishing a blockade, in order to minimize the potential spread of infection to other cities within the network?
Considering the graph below, where each node represents a city and the only means of connection between them is via roads represented by the edges, which cities represent the best candidates for these roles?
A) City 5 as the distribution center and City 4 as the blockade
B) City 3 as the distribution center and City 3 as the blockade
C) City 5 as the distribution center and City 3 as the blockade
D) City 3 as the distribution center and City 4 as the blockade
E) None of the above
Original idea by: Carolina Albuquerque
Estimada Carol, achei sua questão muito interessante. No meu entender, a melhor cidade para bloquear seria a 3, pois sua remoção desconecta o grafo em 3 componentes conexas. Quanto ao centro de distribuição, eu creio que 1, 3 e 5 fariam igualmente bem este papel, pois deles a distância máxima seria 3, a menor possível. Aí é que está o problema. A pessoa vai ficar em dúvida entre as alternativas B e C.
ResponderExcluirBom dia! A resposta seria C. A cidade 5 além da distância máxima ser 3 também está conectada diretamente ao maior número de cidades 5, enquanto a cidade 3 está a apenas 4.
ExcluirBom, precisamos de um critério mais objetivo para determinar o centro de distribuição. Eu modifiquei sua questão, colocando a distância esperada a outras cidades como sendo este critério. Preferi isso ao seu critério, que leva em conta apenas o número de cidades a distâncias 1 e a máxima. O critério que usei leva em conta o número de cidades a todas as distâncias possíveis. Com isto, taquei sua questão no blog. Ah! Modifiquei a ordem das alternativas para ficar mais neutra.
Excluir