Questão 1. Qual das seguintes alternativas poderia ser a ordem em que o Inspetor visita as escolas?
◯ E, F, G, K, I, J, H
◯ E, H, F, G, I, J, K
◯ E, K, G, F, J, H, I
◯ G, E, F, I, H, K, J
◯ G, E, H, K, F, I, J

Passo 1

O que o enunciado nos dá e o que ele pede.
  • São apresentadas cinco alternativas de ordens em que o Inspetor poderia visitar as escolas:
    • E, F, G, K, I, J, H
    • E, H, F, G, I, J, K
    • E, K, G, F, J, H, I
    • G, E, F, I, H, K, J
    • G, E, H, K, F, I, J
  • A pergunta: “Qual das seguintes alternativas poderia ser a ordem em que o Inspetor visita as escolas?”
Observação importante: o enunciado fornecido aqui contém apenas as alternativas. Não há nenhuma informação adicional sobre restrições, mapa, adjacências, precedências, horários ou qualquer diagrama que indique quais transições entre escolas são permitidas ou recomendadas.

Passo 2

Por que não dá para responder diretamente com as informações fornecidas.
  • Para decidir se uma sequência de visitas é possível é preciso conhecer as restrições do problema. Exemplos do tipo de informação que pode ser necessária:
    • um mapa com estradas ou ligações entre escolas (grafo de adjacência), onde só é possível ir de uma escola a outra se houver uma ligação;
    • restrições de precedência (por exemplo: a escola A deve ser visitada antes da B);
    • janelas de horário (visitar X entre tais horas) que tornam algumas ordens inviáveis;
    • custos/distâncias se a ordem tem que obedecer a um critério de otimização (menor distância) ou limites de tempo.
  • Como nenhuma dessas informações foi dada, não há como inferir qual alternativa é válida: duas alternativas diferentes podem ser ambas possíveis ou ambas impossíveis dependendo das regras que não foram especificadas.
Por isso, com o enunciado tal como veio, não é possível escolher uma alternativa correta — falta informação essencial (por exemplo, o grafo/diagrama ou as regras de visita).

Passo 3

Como modelar o problema quando houver um mapa de ligações entre escolas (modelo de grafo) — explicação didática.
  • Representação: modela-se cada escola como um vértice de um grafo G=(V,E), onde V é o conjunto de escolas e cada aresta (u,v)\in E indica que o Inspetor pode ir diretamente de u para v.
  • Verificação de uma ordem candidata: dada uma sequência S=(s_1,s_2,\dots,s_n) (cada s_i é uma escola), para verificar se ela é viável no modelo de grafo basta checar, para todo i=1,\dots,n-1, se (s_i,s_{i+1})\in E (ou \{s_i,s_{i+1}\}\in E, se o grafo for não orientado). Em palavras: cada passo consecutivo na lista tem de corresponder a uma ligação permitida.
  • Procedimento manual simples para checar uma alternativa (para usar na prova):
    1. Pegue a sequência candidata S.
    2. Para cada par consecutivo (s_i,s_{i+1}), consulte o mapa/diagrama e confirme se existe ligação direta.
    3. Se todas as transições existirem, a sequência é possível; se faltarem uma ou mais transições, a sequência é impossível.
  • Exemplo genérico (não vindo do enunciado): suponha que as arestas permitidas são \{(E,F),(F,G),(G,K),(K,I),(I,J),(J,H)\}. Então a sequência E,F,G,K,I,J,H seria viável porque cada par consecutivo está na lista de arestas.

Passo 4

Se o problema for de precedência (ordem com restrições tipo “A antes de B”): modelagem e método (ordenação topológica).
  • Modelagem: usar um grafo direcionado acíclico (DAG) onde uma aresta direcionada A \to B significa “A deve ser visitada antes de B”.
  • O que se pede então: encontrar uma ordenação linear dos vértices que respeite todas as precedências — isto é uma ordenação topológica.
  • Como fazer uma ordenação topológica (método prático para prova, versão de Kahn, passo a passo):
    1. Liste os vértices que têm grau de entrada 0 (nenhuma pré-condição). Coloque-os numa fila.
    2. Enquanto a fila não estiver vazia:
      • remova um vértice v da fila e escreva-o na ordem resultante;
      • para cada aresta v\to w, remova essa aresta do grafo e, se w ficar com grau de entrada 0, coloque w na fila.
    3. Se no final todas as arestas foram removidas, a ordem formada é uma ordenação topológica válida; se restarem arestas, havia um ciclo e não existe ordenação que satisfaça todas as precedências.
  • Para verificar uma alternativa dada, basta confirmar que ela respeita todas as relações A antes de B: para cada restrição A\to B, na sequência candidata o índice de A deve ser menor que o índice de B.

Passo 5

Se o problema for “visitar cada escola exatamente uma vez” sem restrições de ligação direta (problema do tipo Hamiltoniano/TSP) — como checar e métodos básicos.
  • Problema Hamiltoniano: determinar se existe um caminho que passe por todos os vértices exatamente uma vez respeitando as arestas do grafo. Esse problema é difícil em grafos grandes, mas para 7 vértices (caso aqui) é prático testar candidatas manualmente.
  • Método prático (backtracking simplificado, para prova):
    1. Fixe um vértice inicial (ou teste todos, se não estiver fixo).
    2. Tente construir o caminho passo a passo: escolha um vizinho não visitado, avance; se ficar sem vizinhos não visitados, volte (backtrack) e tente outra escolha.
    3. Como há poucos vértices, esse procedimento termina rápido; mas se tiver um diagrama, a verificação de cada alternativa é simplesmente checar pares consecutivos, como no Passo 3.
  • Nota: se o problema pede o melhor caminho por distância (TSP), então é otimização — não basta verificar possibilidade; seria preciso calcular somas de distâncias e comparar.

Passo 6

Exemplo ilustrativo (inventado) de verificação de uma alternativa para fixar o processo mental.
  • Suponha que o diagrama/rotas permite apenas estas transições diretas: (E,F),(F,G),(G,K),(K,I),(I,J),(J,H) (grafo caminho linear).
  • Para a alternativa E, F, G, K, I, J, H verificamos os pares consecutivos:
    • (E,F) existe,
    • (F,G) existe,
    • (G,K) existe,
    • (K,I) existe,
    • (I,J) existe,
    • (J,H) existe.
  • Conclusão do exemplo: a alternativa seria válida nesse diagrama específico. Mas se qualquer uma dessas arestas não existisse no diagrama verdadeiro do enunciado, a alternativa se tornaria inválida.

Passo 7

Conclusão final sobre o enunciado que você mandou.
  • Não há como escolher qual alternativa poderia ser a ordem real do Inspetor porque o enunciado não trouxe o diagrama, as ligações, as precedências nem outra regra que determine quais transições são permitidas.
  • Para responder corretamente é necessário pelo menos uma das seguintes coisas (uma delas basta):
    • o mapa/diagrama com as ligações entre escolas (grafo);
    • a lista de restrições de precedência do tipo “A antes de B”;
    • as janelas de tempo ou outras regras operacionais que limitem ordens possíveis.
Força aí — se você tiver o diagrama ou as restrições, posso checar cada alternativa passo a passo e dizer qual(es) são possíveis. Estou contigo, isso a gente resolve rapidinho.

Resposta

Não é possível determinar qual alternativa é correta porque o enunciado não fornece o diagrama/Mapa de ligações ou as restrições necessárias para verificar a viabilidade das ordens.

Exercícios relacionados