¿Qué es Grafo, matriz de adyacencia?

Un grafo consta de vértices $1, 2, \dots, n$ y de aristas que unen ciertos pares de vértices (pares ordenados si el grafo es dirigido). Su matriz de adyacencia es la matriz $n \times n$ $M$ con $m_{ij} = 1$ si hay una arista de $i$ a $j$, y $0$ en caso contrario. Un camino de longitud $k$ de $i$ a $j$ es una sucesión de $k$ aristas consecutivas que lleva de $i$ a $j$.