Según la disposición y dirección de las aristas y arcos, podemos obtener las siguientes definiciones basándonos en un grafo G:
1. Una cadena es una sucesión finita de vértices-aristas. W= v0e1v1…ekvk.
2. La longitud de una cadena es el numero de aristas|arcos que contiene.
3. Una cadena simple es una cadena con todas sus aristas distintas, no se repite ninguna. En el caso de los arcos se debe tener en cuenta que las direcciones de estos deben concordar con la dirección de la cadena.
4. Una camino es una cadena con todos sus vértices distintos. Como el anterior, pero esta vez son los vértices lo que no se pueden repetir.
5. Una cadena cerrada es una cadena de longitud no nula en donde el vértice inicial y final coinciden.
6. Un ciclo es una cadena simple cerrada con todo sus vértices distintos. Para grafos dirigidos los llamamos circuitos.
Circuito: Cadena simple cerrada y dirigida
CONEXIÓN
7. Diremos que dos vértices u y v están conectados si existe un camino de U a V y viceversa. En el caso de los grafos dirigidos, debería haber dos arcos, uno de U a V y otro de V a U.
8. Un grafo es conexo si todo par de vértices están conectados. No confundir con grafos completos, un grafo puede ser conexo pero no completo, como los siguientes.
9. Un grafo dirigido es fuertemente conexo si para cada par de vértices U y V, existe un camino dirigido que une esos dos vértices.
10. Un grafo dirigido es débilmente conexo si su grafo no dirigido asociado es conexo.
TEOREMAS
La relación de conexión es de equivalencia y por tanto determina una partición en el conjunto de vértices. A los elementos de dicha partición se les denomina componentes conexas del grafo.
Un grafo es conexo si y solo si el número de componentes conexas es 1.