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]