Análise de Algoritmos | Aulas | Bibliografia | WWW | Dicionário | Índice

Território de um vértice

Esta página introduz o conceito de território de um vértice num digrafo.  O conceito é simples e bem conhecido, mas o termo "território" não é muito usado.

Território

Um vértice x é acessível a partir de um vértice r se existe um passeio de r a x.  O território de um vértice r é o conjunto de todos os vértices acessíveis a partir de r.  Se X é o território de um vértice então nenhum arco sai de X:  não existe arco com ponta inicial em X e ponta final fora de X.

Problema do território:  Dado um vértice r de um digrafo, encontrar o território de r.

Exercício

Algoritmo do território

Eis uma primeira tentativa de solução do problema do território. O algoritmo abaixo pinta de preto todos os vértices do território de um vértice r. O digrafo tem vértices 1, …, n e conjunto A de arcos.

O algoritmo está correto, mas não é claro como executar a linha 4 de maneira eficiente. Para enfrentar essa dificuldade, vamos introduzir uma cor intermediária entre o branco e o preto.  Quando um vértice é visitado pela primeira vez, ele se torna cinza. O vértice permanece cinza enquanto seus vizinhos não tiverem sido todos visitados. Só depois que todos os vizinhos do vértice tiverem cor cinza, o vértice fica preto.  Para colocar essa ideia em prática, convém que o digrafo seja representado por suas listas de adjacência Adj[1..n] e não por seu conjunto de arcos.

No fim da execução do algoritmo, todo vértice é branco ou preto. Um vértice v está no território de r se e somente se cor[v]= preto.

No início de cada iteração do bloco de linhas 5-8, o conjunto dos vértices cinza "separa" os vértices pretos dos brancos. Mais precisamente,

1. não existe arco xy tal que x é preto e y é branco  e
2. para todo vértice cinza y distinto de r, existe um arco xy tal que x é preto;
3. todo arco com uma ponta preta tem a outra ponta preta ou cinza.

A propriedade i afirma que a região cinza separa a região preta da branca. De acordo com a propriedade ii, a região cinza está na fronteira da região preta.

A forma do Rascunho-II não é inteiramente satisfatória, pois ainda não está claro como implementar a linha 4. Uma implementação eficiente deve reunir os vértices cinza em algum tipo de lista de onde um vértice possa ser rapidamente retirado e à qual um novo vértice possa ser rapidamente acrescentado.  Nosso rascunho adquire então a seguinte forma final:

O comando Cria-Lista(r) cria uma lista de vértices tendo r como único elemento.  O comando Retira-da-Lista(L) retira um vértice da lista L.  O comando Insere-na-Lista(v,L) insere v em L.  No início de cada repetição do bloco de linhas 6-11, um vértice é

• cinza se está na lista,
• preto se já passou pela lista,  e
• branco se não está nem nunca esteve na lista.

[A linha 6 do código tem um caráter não determinístico, pois dá ao algoritmo a liberdade de escolher qualquer vértice u da lista.  Algumas pessoas ficam incomodadas com esse não determinismo. Mas não há razão alguma para o desconforto, pois o algoritmo funciona corretamente como quer que u seja escolhido.  Comentário análogo pode ser feito sobre da escolha de v na linha 7.]

Exercícios

Consumo de tempo do algoritmo Território

Quanto tempo o algoritmo Território consome no pior caso? Vamos medir esse tempo em relação ao tamanho do digrafo, ou seja, em relação ao número n de vértices e ao número m de arcos do digrafo.  Vamos supor que cada uma das funções que manipula a lista de vértices — Cria-Lista, Retira-da-Lista e Insere-na-Lista — consome tempo constante, ou seja, consome uma quantidade de tempo que não depende de n e m.

O tempo gasto com as operações de inicialização nas linhas 1-4 não passa de  Ο(n) .   Quanto ao bloco linhas 6-11, é melhor não tentar estimar, em separado, o número de iterações do bloco e o tempo gasto com cada iteração. É melhor estimar o tempo total gasto com cada linha dentro desse bloco.  (Imagine que o algoritmo cobra R$1 para executar cada linha e conte a quantia total gasta no fim.)

• Cada vértice entra na lista no máximo uma vez e sai da lista no máximo uma vez. Portanto, as linhas 6 e 10 são executadas no máximo n vezes cada. O número de execuções das linhas 5 e 11 também não passa de n. Assim, o tempo total dedicado às execuções dessas linhas é

  Ο(n) .

• A lista de adjacência de cada vértice é percorrida no máximo uma vez. A soma dos comprimentos de todas as listas de adjacência é igual ao número de arcos do digrafo. Portanto, as linhas 7 a 9 são executadas no máximo m vezes. Assim, o tempo total gasto na execução dessas linhas é

  Ο(m) .

Conclusão: o consumo de tempo do algoritmo Território é

Ο(n+m) .

O algoritmo é, portanto, linear.

Poderíamos ser mais precisos e dizer que o consumo de tempo é  Ο(n′+m′),  sendo n′ o número de vértices no território de r e m′ o número de arcos que têm ambas as pontas no território de r.  Mais ainda: como m′ ≥ n′−1, podemos dizer o consumo de tempo é simplesmente Ο(m′).

Exercícios

URL of this site: http://www.ime.usp.br/~pf/analise_de_algoritmos/
Last modified: Thu Dec 13 07:48:42 BRST 2012
Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística da USP