Algoritmos para Grafos | Índice
Os conceitos de caminho e ciclo são essenciais no estudo de grafos. É preciso fazer distinções um tanto sutis entre caminhos, caminhos simples, passeios, ciclos, e ciclos simples.
Um passeio (= walk) 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 é um arco do grafo. (Note que o inverso de um passeio não é, em geral, um passeio.) Um arco do passeio é qualquer arco v-w do grafo tal que w é o sucessor de v no passeio. Um passeio é fechado (= closed) se tem pelo menos dois arcos e seu primeiro vértice coincide com o último.
Um caminho (= path) em um grafo é um passeio sem arcos repetidos, ou seja, um passeio em que os arcos são todos diferentes entre si. Um caminho é simples se não tem vértices repetidos. Por exemplo, 0-2-7-3-6 é um caminho simples no grafo da figura.
Todos os arcos de um caminho apontam na mesma direção — de um vértice para o seu sucessor. Há quem goste de enfatizar esse fato dizendo caminho dirigido em vez de caminho.
A origem de um caminho é o seu primeiro vértice. O término é o seu último vértice. Se um caminho tem origem s e término t, dizemos que vai de s a t.
O comprimento (= length) de um caminho é o número de arcos do caminho. Se um caminho tem n vértices, seu comprimento é pelo menos n−1; se o caminho é simples, seu comprimento é exatamente n−1.
Exemplo A. Considere, por exemplo, o grafo da figura e veja alguns caminhos nesse grafo:
0-2-7-3-6 7-3 7 2-7-5-4-7-3 5-1-3-6-4-5 5-7-5
Os três primeiros caminhos são simples e têm comprimentos 4, 1 e 0 respectivamente. Os três últimos não são simples e têm comprimentos 5, 5 e 2 respectivamente. Para completar o exemplo, veja cinco sequências de vértices que não são caminhos:
1 3 6 2 7 3 6 4 2 7 5 4 7 5 1 6 3 7 2 0 1 3 7 1 7 3
As duas primeiras não são caminhos porque têm arcos repetidos.
Exemplo B. Considere o grafo cujos vértices são páginas da teia WWW e cujos arcos representam links (referências) de uma página a outra. Um passeio nesse grafo corresponde a uma pessoa que navega no espaço WWW seguindo os links.
Exemplo C. Considere o grafo cujos vértices são aeroportos e cujos arcos são voos comerciais entre aeroportos. Um caminho simples nesse grafo pode representar um roteiro de viagem com conexões.
Ciclos são estruturas muito importantes. São os ciclos que tornam grafos interessantes mas também complexos e difíceis de manipular.
Um ciclo (= cycle) em um grafo é um caminho fechado. (Portanto, todo ciclo tem comprimento maior que 1 e não tem arcos repetidos.) Dizemos que um arco v-w pertence a um dado ciclo (ou que o ciclo passa pelo arco) se o vértice w é o sucessor de v no ciclo. Um ciclo é simples se não tem vértices repetidos exceto pelo último (que coincide com o primeiro).
É apropriado abusar um pouco do conceito de igualdade e tratar dois ciclos simples como iguais se eles têm o mesmo conjunto de arcos, ainda que tenham origens diferentes. Por exemplo, trataremos como iguais os ciclos 6-2-7-3-6, 2-7-3-6-2, 7-3-6-2-7 e 3-6-2-7-3.
Todos os arcos de um ciclo apontam no mesmo sentido — de um vértice do ciclo para o seu sucessor. Há quem goste de enfatizar esse fato dizendo ciclo dirigido no lugar de ciclo.
Exemplo D. Seguem alguns exemplos de ciclos no grafo da figura:
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 tem comprimento 3, e o terceiro tem comprimento 4. Esses três ciclos são simples. Já o último ciclo não é simples. Para completar o exemplo, veja dois passeios que não são ciclos:
6 5-4-7-5-1-3-6-2-7-5