4.1. Introducción y definiciones.
Un grafo G es una tupla G=(V, A), donde V es un conjunto no vacío de vértices y A es un conjunto de aristas o arcos.
Cada arista es un par (v, w), donde v, w pertenecen a V.
Grafo no dirigido: Las aristas no están ordenadas, es decir: (v, w) = (w, v)
Grafos dirigidos (o digrafos): Los pares sí están ordenados: <v, w> ? <w, v>
<v, w> ? w = cabeza de la arista, v = cola de la arista
Un vértice w es adyacente a v sí y sólo si (v, w) (ó <v, w>) pertenece a A.
Camino de un vértice w1 a wq: es una secuencia w1, w2, ..., wq ? V, tal que todas las aristas (w1, w2), ..., (wq-1, wq) ? A.
Longitud de un camino: número de aristas del camino = nº de nodos -1
Camino simple: aquel en el que todos los vértices son distintos (excepto el primero y el último que pueden ser iguales).