O que é Grafo, matriz de adjacência?

Um grafo é formado por vértices $1, 2, \dots, n$ e arestas ligando certos pares de vértices (pares ordenados, no caso de um grafo orientado). Sua matriz de adjacência é a matriz $M$ de tamanho $n \times n$ com $m_{ij} = 1$ se há uma aresta de $i$ para $j$, e $0$ caso contrário. Um passeio de comprimento $k$ de $i$ a $j$ é uma sequência de $k$ arestas consecutivas que leva de $i$ a $j$.