Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Caminhos e territórios

Um caminho (= path) em um grafo é uma seqüê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].

[A definição usual de caminho exige que os vértices sejam distintos dois a dois. Mas nestas notas, por fidelidade ao SGB, não vamos exigir essa condição.]   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 seqüê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; é claro que um caminho simples também não tem arcos repetidos.

Exemplo:  No grafo do exemplo 1 do capítulo O que é um grafo?, a seqüência  (6, d, 0, a, 0, b, 2)  é um caminho.  Já a seqüência  (2, e, 6, d, 0)  não é um caminho.

Exercícios

1. Faça uma lista de todos os caminhos no grafo do exemplo 1 do capítulo O que é um grafo?.

2. No exemplo 1 do capítulo O que é um grafo?, o caminho  (6, d, 0, b, 2)  é simples?  O caminho  (6, e, 2, c, 6, f, 4)  é simples?

3. Suponha que  r  e  s  são dois vértices em um mesmo componente de um grafo.  É verdade que existe um caminho de  r  a  s? É verdade que existe um caminho de  s  a  r?

4. Que aparência tem um caminho na matriz de adjacências do grafo?  Mais precisamente, suponha que (v[0],  v[1],  v[2],  . . . ,  v[k])  é um caminho simples. Como a matriz de adjacências deve ser impressa para que seja fácil perceber o caminho.

Território de um vértice

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).

Exercícios

5. Suponha que  r  é um vértice qualquer.  É verdade que  T(r)  é um componente? E se o grafo for simétrico?

6. Suponha que  r  é um vértice qualquer.  Mostre que o grau de saída de  T(r)  é zero:  gs(T(r)) = 0.

7. Suponha que  R  é um conjunto de vértices tal que  gs(R) = 0.  Para  r  em  R, é verdade que  R = T(r)?

8. Suponha que  r  e  s  são dois vértices quaisquer.  Se s está em T(r), qual a relação entre  T(r)  e  T(s)?  Se s está fora de T(r), é verdade que T(s) é disjunto de T(r)?  Se s está fora de T(r) e r está fora de T(s), é verdade que T(s) é disjunto de T(r)?

9. Qual a relação entre os conceitos de componente e território?