Es un conjunto de puntos (vértices) en el espacio que están conectados por un conjunto de líneas (aristas). Es una estructura de datos, en concreto un tipo abstracto de datos, que consiste en un conjunto de nodos(también llamados vértices) y un conjunto de arcos(aristas) que establecen relaciones entre los nodos. Informalmente se define como G= (V,E), siendo los elementos de V los vértices y los de E, las aristas. Formalmente, un grafo, G, se define como un par ordenado, G(V,E),donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.

Consta de aristas y caminos, donde los vértices son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al numero de aristas de las que es extremo. Se dice que un vértice es ‘par’ o ‘impar’ según lo sea un grado.

· * Vértice adyacentes: si tenemos un par de vértices de un grafo (U. V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y si se dice que U es el vértice inicial y V el vértice adyacente.

· *Vértice aislado: es un vértice de grado cero

· *Vértice terminal: es un vértice de grado 1.

Camino: sea x, y “V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacia de aristas {x, v1}, {v1,v2},…, {vn}. En este caso

· *X e y se llaman los extremos del camino

· *El numero de aristas del camino se llama longitud del camino

· *Si los vértices no se repiten en el camino se dice propio o simple

· *Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.

· *Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.

· *Llamaremos ciclo a un circuito simple

· *Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo.