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

• Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
• Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
• Uma equipe de estudantes desenvolveu um aplicativo para mapear as conexões entre pontos de coleta seletiva em uma…
• Uma cidade quer organizar um sistema de transporte com várias paradas. Cada parada pode estar ligada diretamente a…
• Um grafo tem milhares de vértices, mas cada vértice se liga a poucos outros. Qual estrutura representa esse grafo…
• Em um grafo que representa amizades em uma turma (cada aluno é um vértice e cada amizade é uma aresta), cada aluno tem…

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.