Matriz de Adyacencia: Matriz cuadrada A, donde aij, es el número de aristas que unen el vértice vi con el vj, o el número de arcos que van desde vi hasta vj.
- En grafos no dirigidos es una matriz simétrica, y los bucles cuentan por 2. Además la suma de los elementos de cada columna i o de cada fila i son el grado del vértice vi.
- En grafos dirigidos la suma de las elementos de la fila i es el grado de salida del vértice vi, mientras que la suma de los elementos de una columna j es el grado de entrada del vértice vj.
Al elevar la matriz A a r, se obtiene Ar, otra matriz cuadrada cuyos elementos aij son el número de cadenas de longitud r que van desde vi hasta vj.
Matriz de Incidencia: Cada fila corresponde a un vértice y cada columna a un arco o arista.
- En grafos no dirigidos, el elemento mij puede ser: 0 si vi no es incidene con ej; 1 si vi es incidene con ej; y 2 si en vi, ej forma un bucle.
- En grafos dirigidos, el elemento mij puede ser: 0 si vi no es incidene con ej; 1 si vi es vértice inicial de ej; -1 si vi es vértice final de ej; y 2 si en vi, ej forma un bucle.