Consideramos un grafo G = (V,E) donde V es un conjunto finito (de vértices) del grafo y E ⊆ V × V son las aristas del grafo; es decir (i, j) ∈ E si y solo si los vértices i y j están conectados. En este documento todos los grafos son no dirigidos ((i, j) ∈ E ⇔ (j, i) ∈ E), y no hay bucles en los vértices (∀i ∈ V, (i, i) /∈ E). En estas condiciones, la matriz de adyacencia de G viene dada por A(G) = (aij) donde aij = 1 si (i, j) ∈ E y aij = 0 si aij /∈ E. La matriz A(G) es una matriz 0 − 1, simétrica, de ceros en la diagonal.
