CCT-UFCA/Ciência da Computação/Teoria dos Grafos/Caminhos e Circuitos:

Definições fundamentais

Definição: Um passeio em um grafo $G$ é uma sequência alternada de vértices e arestas, iniciando e terminando em vértices, e tal que cada aresta conecta dois vértices consecutivos na sequência.

Ex.: $W=\{v_{1},v_{1}v_{2},v_{2},v_{2}v_{3},v_{3},...,v_{k-1},v_{k-1}v_{k},v_{k}\}$

Chamamos os vértices $v_{1}$ e $v_{k}$ de $W$ de extremidades do passeio. Os demais vértices são os vértices internos de $W$.

Definição: O comprimento de um passeio é o número de arestas que ele contém.

Definição: Uma trilha é um passeio em que não se repetem arestas.

Definição: Um caminho é um passeio em que não se repetem vértices.

Definição: Um ciclo em $G$ é um passeio fechado em que não se repetem vértices (com exceção dos extremos, que são o mesmo vértice).

• Obs.: Se $v_{1}=v_{k}$, dizemos que o passeio $W$ é fechado. Caso contrário, dizemos que é aberto.
• Obs.: Se existem um passeio $W$ entre $u$ e $v$ em $G$, então dizemos que $u$ alcança $v$ ou que $v$ é alcançado por $u$ em $G$ através de $W$.