Em um grafo não direcionado simples, qual propriedade a matriz de adjacência A (n×n, entradas 0/1) satisfaz em…
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
Em um grafo não direcionado simples, qual propriedade a matriz de adjacência A (n×n, entradas 0/1) satisfaz em relação à sua transposta?
- A) A é anti-simétrica (A = -A^T).
- B) A é ortogonal (A A^T = I).
- C) A é uma matriz diagonal (apenas entradas na diagonal são não nulas).
- D) A matriz de adjacência é simétrica (A = A^T).
- E) A é triangular superior (todas arestas aparecem só acima da diagonal).
✅ Resposta correta: alternativa D
Resolução passo a passo
- Em um grafo não direcionado, se existe a aresta entre os vértices i e j, então também existe a aresta entre j e i, pois a aresta não tem sentido. Por isso, a entrada A[i][j] (que indica a presença da aresta de i para j) deve ser igual a A[j][i].
- Isso significa que A[i][j] = A[j][i] para todos i e j, ou seja, A = A^T. A matriz é simétrica em relação à diagonal principal.
- Por que as outras estão erradas: A) a anti-simetria exigiria A = -A^T, o que forçaria entradas nulas na diagonal e valores negativos, impossível com entradas 0/1 que representam arestas em um grafo não direcionado. B) ortogonalidade (A A^T = I) exigiria que cada linha tivesse exatamente um elemento 1, o que não vale em geral, pois um vértice pode ter vários vizinhos. C) a matriz diagonal só teria arestas laços, não as arestas entre vértices distintos do grafo. E) triangular superior exigiria que as arestas aparecessem só acima da diagonal, mas em grafo não direcionado cada aresta aparece nas duas posições simétricas.
- Portanto, a propriedade válida para qualquer grafo não direcionado simples é a simetria, e a alternativa correta é a D, coincidindo com o gabarito oficial.
💡 Dica: Considere as propriedades da matriz de adjacência de grafos.
Alternativa por alternativa
O aluno pode ter associado 'ser igual à transposta' a outra relação entre matriz e transposta, confundindo simetria com anti-simetria e imaginando que a transposta deveria trocar o sinal das entradas.
Por que engana: Confundir a definição de matriz simétrica com outras propriedades de matrizes, como anti-simetria ou ortogonalidade.
O aluno pode ter lembrado de matrizes com A A^T = I (ortogonais) e aplicado a ideia a qualquer matriz de 0 e 1, sem verificar se a propriedade vale para grafos.
O aluno pode ter confundido a ideia de que a matriz é 'simétrica' com a de que ela só tem valores na diagonal, achando que arestas são representadas apenas por entradas diagonais.
Para cada aresta {u,v} num grafo não direcionado vale A[u][v]=1 e A[v][u]=1; assim todas as entradas fora da diagonal são espelhadas, tornando A igual à sua transposta.
O aluno pode ter entendido que, por ser possível escrever as arestas em uma ordem, a matriz fica apenas acima da diagonal, esquecendo que em grafo não direcionado a aresta aparece nas duas posições simétricas.
Raio-X da questão
matriz de adjacência
avaliacao
propriedades de matrizes · grafos não direcionados
Revisar as propriedades das matrizes de adjacência em grafos não direcionados.
Confundir a definição de matriz simétrica com outras propriedades de matrizes, como anti-simetria ou ortogonalidade.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Dada a matriz de adjacência A (n×n) de um grafo não direcionado, como identificar por inspeção a presença de um laço…
- Em um grafo simples não direcionado, ao adicionar uma aresta entre os vértices i e j (i ? j), como mudam as entradas da…
- Dada a matriz de adjacência A (entradas 0/1) de um grafo simples não direcionado sem laços, qual expressão matricial…
- Matriz de adjacência 4×4 com vértices A,B,C,D: [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]. Avalie se ela representa um…
- Para qual situação a matriz de adjacência é mais indicada para representar um grafo?
- Em um grafo não direcionado representado por uma matriz de adjacência, qual é a complexidade em espaço (variável de…
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