Origen y definición de Grafo

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama), grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad. En cada caso, es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos (vértices) con líneas conectándolos (arcos). 

Ahora bien, un grafo G es un par ordenado G = (V,E), donde:

• V es un conjunto de vértices o nodos, y
• E es un conjunto de arcos o aristas, que relacionan estos nodos.

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, | V | .