Um grafo é um conjunto de vértices, alguns deles conectados a arestas. Os grafos são representados por um par de dois conjuntos, o conjunto de vértices e o conjunto de pares de arestas. Caso o par de arestas (v,u) seja o mesmo que o par (u,v), o par de vértices estão conectados por uma aresta não direcionada. Caso contrário, ou seja, (u, v) é diferente de (v, u) , o par deixa explícito a direção da aresta, pois se (u, v) a aresta vai de u até v. Grafos são direcionados (dígrafos) se todas as suas arestas forem direcionadas.