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,\mathrm{...},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$.