===== Passeios, Caminhos e Ciclos =====

Quando vimos o [[.historiaGrafos| Problema das Sete Pontes de Königsberg]] , estávamos interessados em determinar um roteiro que passasse por todas as pontes apenas uma vez. Para tal, é essencial o conceito de passeios e de caminhos, bem como o de ciclos.

==== Passeio ====

<WRAP round box 100%>
=== Definição: Passeio ===
//Dado um grafo $G=(V, A)$, um passeio em $G$ consiste de uma sequência finita alternada de vértices e arestas, começando e terminando por vértices, tal que cada aresta é incidente ao vértice que a precede e ao que a sucede.//

//Matematematicamente, temos que um passeio em $G$ é uma sequência não vazia $P = (v_0,a_0,v_1,a_1,\cdots,a_{k-1},v_k)$ de vértices ($v_k$) e arestas ($e_k$) de $G$, em que $a_i=\{v_i,v_{i+1}\}$ para todo $i<k$.//

//Os vértices $v_0$ e $v_k$ são a **origem** e o **término** de $P$, respectivamente, ou também chamados de **extremidades**. Além disso, os vértices $v_1,v_2,\dots,v_{k-1}$ são os **vértices internos** de $P$.//

//O **comprimento** de um passeio é o número de arestas de $P$, e denota-se $P^k$., onde $k$ é o comprimento de $P$.//

//Se $v_0=v_k$, o passeio é **fechado**.//
</WRAP>

Assim sendo um passeio em um grafo é uma sequência de vértices dotada da seguinte propriedade: se $v$ e $w$ são vértices consecutivos na sequência então $v-w$ é uma aresta do grafo. Uma aresta do passeio é qualquer aresta $v-w$ do grafo tal que $w$ é o sucessor de $v$ no passeio.

<WRAP round box 100%>
=== Definição: Trajeto ===
//Dado um grafo $G(V, A)$, um **trajeto** em $G$ consiste em um **passeio**, tal que cada aresta aparece apenas uma vez.

Um trajeto no qual o vértice inicial e o final são iguais é chamado de **trajeto fechado.**//
</WRAP>

==== Caminho ====

<WRAP round box 70%>
=== Definição ===
//Dado um grafo $G(V, A)$, um [[.defCaminho| caminho]] em $G$ consiste em um **passeio** onde não há repetições de vértices,isto é, eles são todos distintos.//

//Em outras palavras, um caminho é um **trajeto** onde não há repetição de vértices.//
</WRAP>

Um caminho em um grafo é, então, um passeio sem arestas repetidas, ou seja, um passeio em que as arestas são todas diferentes entre si. Além disso, um caminho é dito **simples** se não tem vértices repetidos.

A origem de um caminho é o seu primeiro vértice. O término é o seu último vértice.  Se um caminho tem origem $x$ e término $y$, dizemos que  vai de $x$ a $y$.

As seguintes observações podem ser feitas:
  * Os vértices finais de um caminho possuem grau $1$ e os demais, vértices intermediários, possuem grau $2$;
  * Para grafos não valorados o comprimento é igual ao números de arestas incluídas no caminho, e em grafos valorados é igual a soma dos valores das arestas;

No exemplo abaixo, temos um caminho $P = P^6$ em $G$, por exemplo:
{{ :grafos:grafo1.png?500 |}}

\\

<WRAP round tip 50%>
=== Veja também: ===
  * [[.HCaminho|$H-$caminho]];
  * [[.independent|Caminhos independentes]].

</WRAP>
==== Ciclos ====

<WRAP round box 95%>
=== Definição ===
//Um **trajeto fechado** no qual nenhum vértice (com exceção do inicial e do final) aparece mais de uma vez é chamado de [[.defCiclo| ciclo]] (**circuito** ou **caminho fechado**).//

//O compriemnto de um ciclo é dado pelo seu número de arestas. O ciclo de tamanho $k$ é chamado de $k$-ciclo e denotado por $C^k$.//

//Um ciclo é simples se não tem vértices repetidos exceto pelo último, que coincide com o primeiro.//
</WRAP>

Ciclos são estruturas importantíssimas. São os ciclos que tornam grafos interesantes, mas também complexos e difíceis de manipular. Dizemos que uma aresta $v-w$ pertence a um dado ciclo( ou que o ciclo passa por este arco) se o vértice $w$ é o sucessor de $v$ no ciclo.

Observe o grafo abaixo:

{{ :grafos:caminhos.png?400 |}}

São exemplos de ciclos neste grafo:

$$5-7-5$$

$$4-7-5-4$$

$$6-2-7-3-6$$

$$5-4-7-3-6-2-7-5$$

O primeiro tem comprimento $2$; o segundo, $3$; e o terceiro, $4$. Esses três ciclos são simples. O último ciclo não é simples.

Para caso de completude, observe que $5-4-7-5-1-3-6-2-7-5$ não constitui um ciclo deste grafo.

\\

<WRAP round box 50%>
=== Proposição ===
//Se $G(V,A)$ é um grafo tal que $d(v) \geq 2$ para todo $v \in V$, então $G$ contém um **ciclo**.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Se $G$ possui laços ou arestas paralelas, não há o que provar. Então, vamos supor que $G$ é um grafo simples. Seja $v_0 \in V$ um vértice arbitrário de $G$. Como $d(v) \geq 2$ para todo $v \in V$, podemos construir um passeio $v_0 \to v_1 \to v_2 \cdots$ indutivamente, escolhendo $v_{i+1}$ como sendo qualquer vértice adjacente a $v_i$ exceto $v_{i-1}$.

Como $G$ possui uma quantidade finita de vértices, em algum momento escolheremos algum vértice, digamos $v_k$, pela segunda vez.

A parte do passeio entre a primeira e a segunda ocorrência de $v_k$ constitui um ciclo. 

<wrap right>$\square$</wrap>
</WRAP>

<WRAP round tip 50%>
=== Veja também: ===
  * [[.circunferencia|Circunferência de $G$]]
  * [[.cintura|$g(G)$ - Cintura de $G$]]
  * [[.chord| Cordas em um grafo]]
</WRAP>


----
<WRAP round info 100%>
=== Referências ===
  * Paulo Feofiloff. [[https://www.ime.usp.br/~pf/algoritInstituto de Matemática e Estatística da Universidade de São Paulo (IME-USP)mos_para_grafos/aulas/paths-and-cycles.html| "Caminhos e Ciclos em grafos"]] . Instituto de Matemática e Estatística da Universidade de São Paulo- IME-USP. Acesso em 21/09/2022.
  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch1.pdf|“Graph Theory”]] .5th Electronic Edition 2016, pp. 01–03. Acesso em 16/09/2022.
  * Valeriano A. de Oliveira. Socorro Rangel. Silvio A. de Araújo. [[https://www.ibilce.unesp.br/Home/Departamentos/MatematicaAplicada/docentes/socorro/caminhoscircuitos.pdf | "Teoria dos Grafos: Caminhos e Circuitos"]] . Instituto de Biociências, Letras e Ciências Exatas -Ibilce-Unesp. Acesso em 21/09/2022.
  * Valeriano A. de Oliveira. Socorro Rangel. Silvio A. de Araújo. [[https://www.ibilce.unesp.br/Home/Departamentos/MatematicaAplicada/docentes/socorro/grafoseulerianos.pdf | "Teoria dos Grafos: Grafos Eulerianos"]] . Instituto de Biociências, Letras e Ciências Exatas -Ibilce-Unesp. Acesso em 21/09/2022.
</WRAP>