Uma equipe de mobilidade urbana modelou as conexões entre 12.000 pontos de ônibus de uma cidade como um grafo…

Questão

Uma equipe de mobilidade urbana modelou as conexões entre 12.000 pontos de ônibus de uma cidade como um grafo não direcionado. Nesse grafo, cada ponto é um vértice e cada ligação direta entre dois pontos é uma aresta. O levantamento identificou 36.000 ligações, número muito menor que a quantidade de pares possíveis de pontos. A equipe precisa escolher uma representação que use memória principalmente para armazenar as ligações existentes, sem reservar espaço para cada par possível de vértices. Com base no texto, qual representação de grafo permite armazenar as conexões existentes com menor desperdício de memória nesse caso?

1. A) Matriz de incidência — cada vértice ocupa uma posição por aresta.
2. B) Lista de adjacência — cada vértice armazena apenas seus vizinhos.
3. C) Matriz de adjacência — cada par de vértices ocupa uma posição.
4. D) Lista de adjacência — cada vértice reserva espaço para todos os possíveis vizinhos.
5. E) Árvore binária — cada vértice possui no máximo dois vizinhos.

✅ Resposta correta: alternativa B

Resolução passo a passo

1. O enunciado descreve um grafo esparso, com 12.000 vértices e apenas 36.000 arestas, bem abaixo do total de pares possíveis (cerca de 71.994.000 pares, ou seja, 12.000 x 11.999 / 2). O objetivo é gastar memória principalmente com as ligações existentes, sem reservar espaço para cada par possível.
2. A lista de adjacência guarda, para cada vértice, apenas a lista de seus vizinhos diretos. Como o grafo é não direcionado, cada aresta aparece duas vezes, então o total de entradas é cerca de 2 x 36.000 = 72.000, mais as listas de cabeçalho de 12.000 vértices. Isso é proporcional ao número de arestas existentes, por isso é a opção com menor desperdício.
3. A matriz de adjacência tem 12.000 x 12.000 = 144 milhões de posições, quase todas vazias (zeros), pois reserva uma posição para cada par de vértices. É exatamente o desperdício que o enunciado quer evitar.
4. A matriz de incidência tem uma linha por vértice e uma coluna por aresta, ou seja, 12.000 x 36.000 = 432 milhões de posições, o que é ainda pior.
5. A alternativa D descreve a lista de adjacência, mas afirma que cada vértice reserva espaço para todos os possíveis vizinhos. Isso é falso para a lista de adjacência, que armazena só os vizinhos existentes, e a descrição se aproxima do que faz a matriz de adjacência.
6. A árvore binária não serve como representação geral: uma árvore com 12.000 vértices tem no máximo 11.999 arestas, e o enunciado fala em 36.000 ligações, além de a árvore binária impor limite de dois vizinhos que não se aplica ao grafo.
7. Conclusão: a alternativa correta é a B, que coincide com o gabarito oficial.

💡 Dica: Identifique qual estrutura armazena apenas as conexões existentes em um grafo esparso.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Um sistema portátil registra a corrente gerada em um eletrodo de trabalho durante um pulso de 4 segundos. Para comparar…
• Em um protótipo computacional que monitora a salinidade de um tanque, dois eletrodos ficam imersos na água e são usados…
• Em uma lavanderia, uma pessoa instala dois eletrodos próximos ao piso, ligados a uma entrada digital de um controlador…
• Em uma demonstração de interface cérebro-computador, eletrodos colocados sobre o couro cabeludo captam sinais elétricos…
• Em um protótipo de interface computacional controlada por sinais musculares, cada canal utiliza um eletrodo para captar…
• Em uma prótese controlada por sinais musculares, eletrodos na pele captam a atividade elétrica e a enviam ao sistema…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.