Um grafo G = (X,A) é uma estrutura composta por um conjunto X de elementos chamados vértices ou nós e um conjunto A de pares de vértices, chamados arcos ou arestas. A representação gráfica de um grafo é feita por pontos (vértices) e linhas (arestas) unindo estes pontos. Quanto as características de seus arcos, um grafo pode ser orientado e não orientado São orientados quando seus arcos possuem uma orientação definida , ou seja , um nó do arco é definido como origem do mesmo e o outro como destino. E, não orientado, quando não existe esta noção de direção. Valorado e não valorado Um grafo é valorado, quando existem valores atribuídos a cada um dos seus arcos. Exemplo disto ocorre quando se está representando uma rede viária e se atribui a cada arco os valores correspondentes às distância entre interseções ( vértices). Planar e não-planar Um grafo planar é aquele em que os arcos somente se cruzam sobre um nó, podendo consequentemente ser projetado sobre um plano, sem perder suas características. Um grafo não-planar, no entanto, quando projetado sobre um plano, apresenta interseções de arcos não coincidentes com um nó, em função de sua estrutura espacial.