Dada a matriz de adjacência A (entradas 0/1) de um grafo simples não direcionado sem laços, qual expressão…
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 (entradas 0/1) de um grafo simples não direcionado sem laços, qual expressão matricial fornece o número de triângulos (ciclos de comprimento 3) presentes no grafo?
- A) trace(A) + 3
- B) trace(A^4) / 12
- C) trace(A^3) / 2
- D) trace(A^2) / 3
- E) trace(A^3) / 6
✅ Resposta correta: alternativa E
Resolução passo a passo
- Lembre que a entrada (i,j) de A^k conta os passeios de comprimento k de i até j. Logo, a entrada (i,i) de A^3 conta os passeios fechados de comprimento 3 que partem e chegam em i. Passo 2: Um triângulo {i,j,k} gera passeios fechados de comprimento 3 da forma i-j-k-i. Ele pode ser percorrido começando em qualquer um dos 3 vértices e em 2 sentidos, o que dá 6 passeios fechados por triângulo. Passo 3: Como trace(A^3) soma as entradas da diagonal, ela conta cada triângulo exatamente 6 vezes. Assim, o número de triângulos é trace(A^3)/6. Passo 4: Verificação com K3 (triângulo, 3 vértices e 3 arestas): A^3 tem diagonal igual a 2 em cada vértice, pois de cada vértice há 2 passeios fechados de comprimento 3. Então trace(A^3)=6 e 6/6=1 triângulo, que é o correto. Passo 5: Por que as outras estão erradas: A) trace(A)+3 é sempre 3 em grafo sem laços, pois trace(A)=0, então não depende do grafo; B) trace(A^4)/12 conta passeios de comprimento 4, que incluem ciclos de comprimento 4 e outras estruturas, não triângulos; C) trace(A^3)/2 não corrige a contagem de 6 passeios por triângulo, e daria 3 para K3; D) trace(A^2)/3 vale 2m/3, pois trace(A^2) é a soma dos graus, e não conta triângulos. Passo 6: Portanto a resposta correta é a alternativa E, concordando com o gabarito oficial.
💡 Dica: Considere a multiplicação de matrizes para encontrar a solução.
Alternativa por alternativa
Acredita que o traço da matriz de adjacência, somado a uma constante, pode contar triângulos, sem perceber que trace(A) é sempre zero em grafo sem laços e que a expressão não depende da estrutura do grafo.
Confunde o comprimento do passeio fechado com o comprimento do ciclo, supondo que A^4 identifica triângulos quando na verdade conta passeios de comprimento 4, que correspondem a ciclos de comprimento 4 e outras configurações.
Reconhece que trace(A^3) conta triângulos, mas não percebe que cada triângulo aparece 6 vezes (3 vértices iniciais e 2 sentidos), e divide por 2 em vez de 6.
Por que engana: Confundir a operação de traço com a contagem de ciclos, aplicando a fórmula errada para o cálculo de triângulos.
Usa trace(A^2), que é a soma dos graus (2 vezes o número de arestas), e supõe que dividir por 3 dá triângulos, confundindo caminhos de comprimento 2 com ciclos de comprimento 3.
A diagonal de A^3 conta walks fechados de comprimento 3 começando em cada vértice; cada triângulo contribui com 6 walks distintos (3 escolhas de vértice inicial × 2 orientações), logo divide-se por 6.
Raio-X da questão
triângulos em grafos
avaliacao
matrizes e operações matriciais · teoria dos grafos
Revisar a teoria sobre matrizes de adjacência e ciclos em grafos.
Confundir a operação de traço com a contagem de ciclos, aplicando a fórmula errada para o cálculo de triângulos.
ciencia_tecnologia
pensamento_critico
cientifico
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 não direcionado simples, qual propriedade a matriz de adjacência A (n×n, entradas 0/1) satisfaz em relação à…
- 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…
- Descreva em passos um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne todas as…
- 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…
- Qual das seguintes opções melhor representa uma matriz 3x3?
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