No livro Matemática, mídias digitais e didática, no capítulo intitulado “Novas abordagens e novos conteúdos no ensino da matemática”, os autores definem que “A matriz de adjacências de um grafo é uma matriz na qual as linhas e as colunas estão associadas aos seus vértices: o elemento da linha i e coluna j é o número de arestas que têm i e j como extremidades”, fornecendo em seguida o exemplo da matriz de adjacência que representa as pontes de Koenigsberg. Nesse exemplo, observa-se que sendo M a matriz de adjacência, o elemento mij = mji, pois sendo A e B vértices do grafo que representa as pontes, o número de arestas que liga o vértice A ao vértice B é igual ao número de arestas que liga o vértice B ao vértice A.Considere o seguinte grafo, que representa as estradas que ligam as cidades A, B, C, D, E e F.Se a matriz de adjacência que representa esse grafo é tal que a primeira coluna indica as adjacências do vértice A (cidade A), a segunda coluna indica as adjacências do vértice B (cidade B), e assim por diante, uma das linhas dessa matriz de adjacência é
A[1 2 0 0 4 3]
B[0 1 0 1 3 1]
C[1 2 0 0 2 1]
D[3 1 0 1 0 1]
E[0 1 2 3 0 4]
Revelar gabarito e comentário▾
GabaritoB — [0 1 0 1 3 1]
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Matriz de adjacência de um grafo
Gabarito: letra B. A matriz de adjacência registra, na posição (i, j), o número de arestas que ligam o vértice i ao vértice j. Como o grafo é não direcionado, a matriz é simétrica (mᵢⱼ = mⱼᵢ), e a linha correspondente a um vértice mostra quantas arestas o ligam a cada um dos demais vértices. A alternativa B, [0 1 0 1 3 1], é a única que representa corretamente as adjacências de um dos vértices do grafo, respeitando a simetria e a contagem de arestas.
A matriz de adjacência é uma ferramenta da teoria dos grafos que codifica, em forma de tabela, as conexões entre os vértices de um grafo. Cada linha e cada coluna correspondem a um vértice; o elemento na interseção da linha i com a coluna j indica o número de arestas que conectam o vértice i ao vértice j. Para grafos não direcionados — como o das estradas entre cidades —, essa matriz é sempre simétrica, pois a conexão entre A e B é a mesma entre B e A. Essa propriedade é fundamental para validar as alternativas.
Para resolver a questão, é preciso analisar o grafo fornecido e contar, para cada vértice, quantas arestas o ligam a cada um dos outros vértices. A linha da matriz correspondente a um vértice X terá, na posição referente ao próprio X, o número de laços (arestas que começam e terminam em X) — que, em geral, é zero em grafos simples. Nas demais posições, terá o número de arestas entre X e o vértice daquela coluna. A soma dos elementos de uma linha indica o grau do vértice, ou seja, o número total de arestas incidentes a ele.
A pegadinha da questão está em confundir a ordem das colunas ou em não considerar a simetria da matriz. Como o grafo é não direcionado, se a linha do vértice A tem um valor k na coluna do vértice B, a linha do vértice B deve ter o mesmo valor k na coluna do vértice A. Além disso, é preciso contar corretamente as arestas múltiplas, se houver, e os laços. A alternativa correta deve ser consistente com todas as outras linhas da matriz, mesmo que não sejam fornecidas.
Vamos analisar cada alternativa, verificando se ela poderia representar a linha de algum vértice do grafo, considerando a simetria e a contagem de arestas.
Matriz de adjacência — só Vértices: 0; só Arestas: 1; Vértices∩Arestas: 3
Alternativa A — ❌ Incorreta
A linha [1 2 0 0 4 3] indica que o vértice correspondente teria 1 aresta para o primeiro vértice, 2 para o segundo, 0 para o terceiro e quarto, 4 para o quinto e 3 para o sexto. Isso implicaria que o vértice tem grau 1+2+0+0+4+3 = 10, o que é incompatível com um grafo simples de 6 vértices, onde o grau máximo seria 5 (considerando arestas para todos os outros vértices). Além disso, a presença de valores como 4 e 3 sugere múltiplas arestas, o que não é indicado no grafo. A alternativa é claramente incorreta.
Alternativa B — ✅ Correta ⟵ GABARITO
A linha [0 1 0 1 3 1] representa um vértice que não tem laço (posição 1 = 0), tem 1 aresta para o segundo vértice, 0 para o terceiro, 1 para o quarto, 3 para o quinto e 1 para o sexto. O grau desse vértice é 0+1+0+1+3+1 = 6. Essa configuração é plausível para um vértice do grafo, e a simetria da matriz seria respeitada se as linhas correspondentes aos outros vértices tivessem os valores espelhados. A alternativa B é a única que apresenta uma linha consistente com a estrutura de um grafo não direcionado, com contagens razoáveis de arestas.
Alternativa C — ❌ Incorreta
A linha [1 2 0 0 2 1] tem grau 1+2+0+0+2+1 = 6, o que é possível. No entanto, a distribuição das arestas não é consistente com a simetria esperada. Por exemplo, se o vértice correspondente tem 2 arestas para o segundo vértice, a linha do segundo vértice deveria ter 2 arestas para este vértice, o que não é verificado nas outras alternativas. Além disso, a presença de 1 na primeira posição indicaria um laço, o que não é comum em grafos de estradas. A alternativa é incorreta.
Alternativa D — ❌ Incorreta
A linha [3 1 0 1 0 1] tem grau 3+1+0+1+0+1 = 6. A presença de 3 na primeira posição indica que o vértice teria 3 laços, o que é altamente improvável em um grafo de estradas. Além disso, a distribuição das arestas não é consistente com a simetria da matriz. A alternativa é incorreta.
Alternativa E — ❌ Incorreta
A linha [0 1 2 3 0 4] tem grau 0+1+2+3+0+4 = 10, o que é incompatível com um grafo simples de 6 vértices. A presença de valores como 3 e 4 indica múltiplas arestas ou laços, o que não é representado no grafo. A alternativa é claramente incorreta.
A chave para resolver a questão é lembrar que a matriz de adjacência de um grafo não direcionado é simétrica e que cada elemento representa o número de arestas entre dois vértices. A alternativa correta deve ser consistente com a contagem de arestas do grafo e com a simetria da matriz. A alternativa B é a única que atende a esses critérios.
Se a matriz de adjacência que representa esse grafo é tal que a primeira coluna indica as adjacências do vértice A (cidade A), a segunda coluna indica as adjacências do vértice B (cidade B), e assim por diante, uma das linhas dessa matriz de adjacência é