Um caminho (= path) em um grafo é uma sequência (v[0], a[1], v[1], a[2], v[2], … , a[k], v[k]) em que, para cada i, a[i] é um arco que
sai do vértice v[i−1] e entra no vértice v[i].
Um caminho é um animal dirigido
:
todos os seus arcos apontam do vértice anterior para o seguinte.
Dizemos que v[0]
é a origem
desse caminho e que
v[k] é o
término.
Dizemos também esse caminho
vai de v[0]
a v[k].
Às vezes é conveniente deixar os arcos do caminho subentendidos e dizer que o caminho é a sequência (v[0], v[1], v[2], … , v[k]) de vértices.
Nossa definição de caminho admite coisas que podem parecer estranhas à primeira vista. Assim, por exemplo, um caminho pode passar duas ou mais vezes por um mesmo vértice ou por um mesmo arco. Diremos que um caminho é simples (= simple path) se não tem vértices repetidos (e portanto também não tem arcos repetidos).
Exemplo: No grafo do exemplo 1 do capítulo O que é um grafo?, a sequência (6, d, 0, a, 0, b, 2) é um caminho. Já a sequência (2, e, 6, d, 0) não é um caminho.
Diremos que um vértice v pode ser alcançado a partir de um vértice r se existe um caminho de r a v. (O caminho não precisa ser simples; mas se existe algum caminho de r a v então também existe um caminho simples de r a v.)
O território de um vértice r é o conjunto de todos os vértices que podem ser alcançados a partir de r. (Note que não faz sentido falar de território sem mencionar um vértice: só faz sentido falar de território de um vértice.) Vamos denotar o território de r por T(r).