A figura a seguir apresenta o grafo associado às Pontes de Koenigsberg:
(Matemática, Mídias Digitais e Didática https://www.ufrgs.br/espmat/livros/livro2-matematica_midiasdigitais_didatica.pdf)
A matriz de adjacência associada a esse grafo é:
GabaritoA — \begin{pmatrix} 0 & 2&0&1 \\ 2 & 0&2&1\\0 & 2&0&1\\1 & 1&1&0 \end{pmatrix}
Gabarito: letra A. A matriz de adjacência correta é a que registra o número de arestas (pontes) entre cada par de vértices (regiões da cidade), e o grafo das Pontes de Koenigsberg tem exatamente as multiplicidades 2, 2, 2 e 1 nas arestas — por isso os elementos 2 aparecem nas posições (1,2), (2,1), (2,3), (3,2), (2,4) e (4,2), e o elemento 1 nas posições (1,4), (4,1), (3,4) e (4,3). A alternativa A é a única que reproduz fielmente essa estrutura.
A matriz de adjacência é uma ferramenta da teoria dos grafos que codifica, em uma tabela quadrada, as conexões entre os vértices de um grafo. Cada linha e cada coluna correspondem a um vértice; o elemento na posição (i, j) indica quantas arestas ligam o vértice i ao vértice j. Quando o grafo é não direcionado (as arestas não têm sentido), a matriz é simétrica: o elemento (i, j) é igual ao elemento (j, i). Além disso, a diagonal principal (i = j) registra laços (arestas que saem e voltam ao mesmo vértice) — que não existem neste grafo, por isso todos os elementos da diagonal são 0.
No caso específico das Pontes de Koenigsberg, o problema clássico consiste em quatro regiões da cidade (dois lados do rio e duas ilhas) conectadas por sete pontes. O grafo associado tem quatro vértices (um para cada região) e sete arestas (uma para cada ponte). A peculiaridade que torna o problema famoso é que algumas regiões são conectadas por mais de uma ponte: entre duas regiões há duas pontes paralelas, e entre outras duas também há duas pontes paralelas. É exatamente essa multiplicidade que a matriz de adjacência precisa capturar — e é o que diferencia a alternativa correta das demais.
Para construir a matriz, basta contar, para cada par de vértices, quantas arestas os conectam. Se entre dois vértices há duas pontes, o elemento correspondente é 2; se há uma ponte, o elemento é 1; se não há ponte, o elemento é 0. A alternativa A é a única que apresenta os valores 2 nas posições corretas (indicando as duas pontes duplas) e 1 nas posições das pontes simples, mantendo a simetria exigida por um grafo não direcionado. As demais alternativas ou trocam os valores 2 por 1 (perdendo a informação das pontes duplas), ou posicionam os 2 em lugares errados, ou quebram a simetria da matriz.
A pegadinha central desta questão é justamente a multiplicidade das arestas: o candidato que apenas verifica se há ou não conexão entre os vértices (usando 0 e 1) cai nas alternativas B ou D, que são matrizes de adjacência de um grafo simples (sem arestas múltiplas). A alternativa A é a única que representa corretamente o multigrafo das Pontes de Koenigsberg, com os valores 2 indicando as pontes duplas. Guarde essa distinção: matriz de adjacência de grafo simples usa apenas 0 e 1; matriz de adjacência de multigrafo usa o número de arestas entre cada par de vértices.
A matriz apresentada é:
Ela é simétrica (o elemento (i,j) é igual ao (j,i)), tem diagonal principal nula (não há laços) e registra corretamente as multiplicidades: entre os vértices 1 e 2 há 2 arestas; entre 2 e 3 há 2 arestas; entre 1 e 4 há 1 aresta; entre 2 e 4 há 1 aresta; entre 3 e 4 há 1 aresta. A soma de todos os elementos (ignorando a diagonal) é 2+2+2+1+1+1 = 9, que corresponde a 2 × 7 = 14? Não — na verdade, cada aresta é contada duas vezes (uma em cada direção), então a soma dos elementos acima da diagonal é 2+2+1+1+1 = 7, exatamente o número de pontes. Isso confirma que a matriz está correta.
A matriz é:
Esta matriz representa um grafo simples, onde todos os elementos são 0 ou 1. Ela ignora completamente as pontes duplas do problema: entre os vértices 1 e 2, e entre 2 e 3, deveria haver o valor 2, mas aqui há apenas 1. O erro é a ausência da multiplicidade das arestas — o candidato que conta apenas se há conexão (sim/não) cai nesta alternativa.
A matriz é:
Esta matriz tem dois problemas: primeiro, o elemento (1,2) é 1, mas deveria ser 2 (há duas pontes entre os vértices 1 e 2); segundo, o elemento (1,4) é 2, mas deveria ser 1 (há apenas uma ponte entre os vértices 1 e 4). Além disso, a matriz não é simétrica: o elemento (1,4) é 2, mas o elemento (4,1) é 1 — o que é impossível em um grafo não direcionado. O erro é a troca das multiplicidades entre pares de vértices.
A matriz é:
Esta matriz tem dois erros graves: primeiro, assim como a alternativa B, ela usa apenas 0 e 1, ignorando as pontes duplas (deveria haver 2 entre os vértices 1 e 2, e entre 2 e 3). Segundo, ela não é simétrica: o elemento (3,1) é 1, mas o elemento (1,3) é 0 — o que viola a definição de matriz de adjacência de grafo não direcionado. O erro é a combinação de perda da multiplicidade e quebra de simetria.
A matriz é:
Esta matriz tem um erro de posicionamento: o elemento (3,1) é 2, mas deveria ser 0 (não há ponte entre os vértices 3 e 1); e o elemento (3,2) é 0, mas deveria ser 2 (há duas pontes entre os vértices 3 e 2). Além disso, ela não é simétrica: o elemento (3,1) é 2, mas o elemento (1,3) é 0. O erro é a troca das posições das arestas duplas, deslocando-as para pares de vértices que não têm conexão.
A banca explora a confusão entre grafo simples e multigrafo. Em um grafo simples, a matriz de adjacência usa apenas 0 e 1; mas as Pontes de Koenigsberg formam um multigrafo, com pontes duplas entre alguns pares de regiões. O candidato que não percebe isso marca a alternativa B ou D, que são matrizes de grafo simples. Fique atento: quando o problema menciona "pontes" ou "arestas múltiplas", a matriz deve registrar o número de arestas, não apenas a existência de conexão.
Para conferir se a matriz de adjacência está correta, verifique três coisas: (1) a diagonal principal deve ser toda zero (não há laços); (2) a matriz deve ser simétrica (grafo não direcionado); (3) a soma dos elementos acima da diagonal deve ser igual ao número de arestas do grafo. No caso das Pontes de Koenigsberg, a soma acima da diagonal é 2+2+1+1+1 = 7, exatamente o número de pontes. Se alguma alternativa não satisfizer esses três critérios, ela está errada.
Gabarito: letra A
Link permanente: /questoes/vu219173