Dada a matriz de adjacência A (n×n) de um grafo não direcionado, como identificar por inspeção a presença de…
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
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 (loop) no vértice i?
- A) Verificar se A[i][j] = 1 para algum j diferente de i.
- B) Achar se existem 0s na diagonal A[i][i] da matriz.
- C) Verificar se a entrada diagonal A[i][i] é 1; A[i][i]=1 indica um laço no vértice i.
- D) Contar quantos vértices têm grau 2 no grafo.
- E) Analisar se todos os vértices são conectados entre si.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Na matriz de adjacência de um grafo, a entrada A[i][j] indica se existe uma aresta ligando o vértice i ao vértice j (1 se existe, 0 se não existe).
- Um laço é uma aresta que liga um vértice a ele mesmo. Essa aresta aparece na posição em que a linha e a coluna são o mesmo vértice, ou seja, na diagonal principal da matriz, A[i][i].
- Portanto, para verificar por inspeção se existe laço no vértice i, basta olhar a entrada A[i][i]: se for 1, há um laço em i; se for 0, não há.
- A alternativa A está errada, pois A[i][j] = 1 com j diferente de i indica uma aresta entre dois vértices distintos, não um laço.
- A alternativa B está errada, pois zeros na diagonal indicam justamente ausência de laços; o que interessa é a presença de 1 na diagonal, e não a existência de 0s.
- A alternativa D está errada, pois contar vértices de grau 2 não identifica laços; além disso, em grafos com laços o grau depende da convenção adotada.
- A alternativa E está errada, pois conectividade do grafo é uma propriedade global e não informa se há laço em um vértice específico.
- Conclusão: o gabarito C está correto, pois a resposta correta é verificar se A[i][i] = 1.
💡 Dica: Verifique os elementos da diagonal principal da matriz.
Alternativa por alternativa
O aluno acredita que qualquer 1 fora da diagonal da linha i representa um laço, confundindo a aresta entre dois vértices distintos com uma aresta que retorna ao próprio vértice.
O aluno inverte a leitura da diagonal: pensa que zeros na diagonal indicam laços, quando na verdade um zero em A[i][i] indica justamente ausência de laço.
Por que engana: Confundir a verificação da diagonal da matriz, achando que a presença de 0s indica um laço, quando na verdade é o contrário.
Um laço liga o vértice a si próprio, o que aparece na matriz de adjacência como 1 na posição (i,i). Em um grafo simples essas entradas geralmente são 0.
O aluno associa laço a grau 2, possivelmente lembrando que laços contribuem com 2 para o grau em alguns contextos, mas sem perceber que contar vértices de grau 2 não identifica a presença de laço em um vértice específico.
O aluno confunde a propriedade de conectividade do grafo como um todo com a existência de laços em um vértice, achando que um grafo conexo ou não conexo revela algo sobre laços locais.
Raio-X da questão
matriz de adjacência
avaliacao
matriz de adjacência · grafo não direcionado
Revisar a definição de laços em grafos e matrizes de adjacência.
Confundir a verificação da diagonal da matriz, achando que a presença de 0s indica um laço, quando na verdade é o contrário.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Dada a matriz de adjacência A (entradas 0/1) de um grafo simples não direcionado sem laços, qual expressão matricial…
- Em um grafo não direcionado simples, qual propriedade a matriz de adjacência A (n×n, entradas 0/1) satisfaz em relaçã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…
- 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…
- Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como…
- Dado um grafo não direcionado fornecido como matriz de adjacência, qual condição sobre os graus dos vértices e a…
🔎 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