Em um grafo simples não direcionado, ao adicionar uma aresta entre os vértices i e j (i ? j), como mudam as…

Questã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 A? Explique em termos da variável A[i][j].

1. A) As entradas A[i][j] e A[i][i] se tornam 1, enquanto A[j][i] é 0.
2. B) As entradas A[i][j] e A[j][i] passam a valer 1; a diagonal não é alterada.
3. C) As entradas A[i][j] e A[j][i] tornam-se 0 e a diagonal é alterada.
4. D) Apenas A[i][j] passa a ser 1, e A[j][i] permanece 0.
5. E) As entradas A[i][j] e A[j][i] são alteradas para -1.

✅ Resposta correta: alternativa B

Resolução passo a passo

1. Em um grafo simples não direcionado, a matriz de adjacência A é simétrica, pois a aresta entre i e j existe nos dois sentidos. Assim, adicionar a aresta {i, j} deve alterar as duas posições A[i][j] e A[j][i].
2. Como a aresta é adicionada, essas duas entradas passam a valer 1, indicando que i e j são adjacentes.
3. O enunciado diz que i é diferente de j (i ≠ j). Logo, a aresta não é um laço e a diagonal principal, formada por A[i][i] e A[j][j], não é alterada.
4. Verificação das demais alternativas: A está errada porque A[i][i] não muda (não há laço) e A[j][i] deveria ser 1, não 0. C está errada porque a adição de aresta gera 1, não 0, e a diagonal não é modificada. D está errada porque, em grafo não direcionado, a simetria exige que A[j][i] também valha 1. E está errada porque a matriz de adjacência usa 0 e 1 para indicar ausência ou presença de aresta, e não valores negativos.
5. Portanto, a alternativa correta é a B, que coincide com o gabarito oficial.

💡 Dica: Considere a definição de matriz de adjacência para grafos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resoluçã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 à…
• Ao representar um grafo não direcionado, como a aresta que conecta dois vértices é geralmente considerada?
• Em um grafo não direcionado, como se representa a relação entre dois vértices?
• 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 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 uma lista de adjacência que representa um grafo ponderado, como atualizar de forma consistente o campo 'peso' da…

Todas as questões de Construir conhecimento usando técnicas e tecnologias computacionais, produzindo informação e/ou artefatos de forma criativa, com respeito às questões legais, que proporcionem experiências para si e os demais.