Para qual situação a matriz de adjacência é mais indicada para representar um grafo?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para qual situação a matriz de adjacência é mais indicada para representar um grafo?
- A) Quando o grafo é esparso
- B) Quando as conexões são muitas
- C) Quando não há ciclos
- D) Quando todos os vértices são isolados
- E) Quando se quer evitar redundâncias
✅ Resposta correta: alternativa B
Resolução passo a passo
- A matriz de adjacência é uma tabela n por n, em que n é o número de vértices. Cada posição (i, j) indica se existe uma aresta ou arco ligando o vértice i ao vértice j, usando 1 para existe e 0 para não existe. Ela ocupa sempre n^2 posições, independentemente de quantas conexões existam.
- Como o espaço é fixo, a matriz compensa quando o grafo tem muitas conexões, ou seja, quando há muitas arestas em relação ao número possível de pares de vértices (grafo denso). Nesse caso, quase todas as posições são úteis e a consulta direta de 'existe ligação entre i e j?' é rápida, pois basta olhar uma posição.
- Por isso a alternativa B está correta. Gabarito oficial e resolução coincidem.
- A alternativa A está errada, pois em grafos esparsos a matriz fica cheia de zeros, desperdiçando memória; a lista de adjacência é mais indicada nesse caso.
- A alternativa C está errada, pois a presença ou ausência de ciclos não determina a escolha da representação; a matriz serve para qualquer grafo.
- A alternativa D está errada, pois vértices isolados geram linhas e colunas inteiras de zeros, o que torna a matriz ainda menos eficiente.
- A alternativa E está errada, pois a matriz é, por natureza, redundante (muitos zeros e, em grafos não dirigidos, simetria), sendo justamente a estrutura que não evita redundâncias.
💡 Dica: Considere as características dos grafos e suas representações.
Alternativa por alternativa
Imagina que a matriz é boa para grafos com poucas arestas, achando que a representação deve acompanhar a quantidade pequena de conexões. Não percebe que a matriz guarda todas as posições, inclusive os muitos zeros.
Por que engana: Confundir a aplicabilidade da matriz de adjacência, pensando que é melhor para grafos esparsos, quando na verdade é mais eficiente para grafos densos.
Facilita a verificação de conexões entre vários vértices.
Associa a estrutura do grafo, como a existência de ciclos, à escolha da representação. Confunde uma propriedade do grafo com o critério de eficiência da matriz de adjacência.
Supõe que vértices sem conexões simplificariam a matriz, sem notar que cada vértice isolado ainda ocupa uma linha e uma coluna de zeros. O número de posições continua n^2.
Acredita que, por a matriz ser organizada em tabela, ela evitaria redundâncias. Na prática, a matriz costuma ser redundante, com muitos zeros e informação repetida em grafos não dirigidos.
Raio-X da questão
matriz de adjacência
avaliacao
conceito de grafo · representacao de grafos
Revisar as representações de grafos e suas aplicações.
Confundir a aplicabilidade da matriz de adjacência, pensando que é melhor para grafos esparsos, quando na verdade é mais eficiente para grafos densos.
pensamento_critico
cientifico
Questões parecidas com resolução
- Em uma representação de grafo, qual o propósito de uma matriz de adjacência na organização dos dados dos vértices e…
- Em qual situação a utilização de grafos é mais apropriada?
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
- Para modelar conexões entre usuários em uma rede social com milhões de usuários e grau médio pequeno, qual representação…
- Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…
Todas as questões de Organização e representação da informação
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog