Podemos definir grafo como una terna G = (V, E, f) donde V representa un conjunto de vértices o nodos, E un conjunto de ejes y f una aplicación que a cada elemento de E le hace corresponder un par de elementos de V, es decir, a cada arista le hacemos corresponder un par de vértices.

Si se puede recorrer un eje de un grafo desde un vértice a otro por ambas direcciones nos referimos a una arista. A un grafo constituido por aristas se le denomina grafo no dirigido.

Si se puede recorrer un eje de un grafo desde un vértice a otro pero por una única dirección nos referimos a un arco. A un grafo constituido por arcos se le denomina grafo dirigido o digrafo.

Si dos nodos son unidos por más de un eje, al grafo se le denomina multigrafo.

La conexidad de un grafo determina la posibilidad de seguir caminos en grafos a través de los ejes. Si se puede llegar a un vértice desde otro cualquiera a través de los ejes, respetando el sentido decimos que el grafo es conexo. Si hay vértices inaccesibles, el grafo no es conexo.

El grado de un vértice es el número de aristas o arcos que entran a un vértice (grado de entrada) o que salen de él (grado de salida).

Si dos vértices se encuentran comunicados por una secuencia de ejes decimos que existe un camino entre esos dos vértices. Si se puede salir de un vértice y llegar a dicho vértice por una secuencia de ejes respetando el sentido decimos que existe un ciclo para ese vértice.

Además de los conceptos de la Teoría de Grafos existen diversos algoritmos que ayudan a resolver problemas apoyándonos en este tipo de estructuras cómo pueden ser caminos mínimos, flujos, etc...