terça-feira, junho 06, 2006

 

Distância nó-arco numa rede


Considere-se a distância mais curta do nó j a cada ponto do arco (r, s). Para algum ponto do arco (r, s), esta distância tem o seu valor máximo. Esta distância máxima do nó j a qualquer ponto no arco (r, s) é denotada por d' (j, (r, s)) e chama-se distância nó-arco.

Se o arco (r, s) não tem direcção, há duas meaneiras de ir do nó j ao ponto f em (r, s): via nó r ou via nó s. Naturalmente, selecciona-se a mais curta das duas rotas. Se estas duas rotas têm distâncias desiguais, então alguns pontos na vizinhança do ponto f do arco(r, s) estão ainda mais afastados do nó j. Por exemplo, na Figura 1 (Localização mediana absoluta geral), o ponto 0,25 do arco (3, 4) está a 1,25 unidades ou 2,75 unidades do nó 2, conforme se vá via nó 3 ou via nó 4. Se o f é aumentado de 0,25 para 0,26, a distância mais curta do nó 2 ao ponto 0,26 do arco (3, 4) é o min {1,26; 2,74} = 1,26. Estas duas distâncias são iguais no ponto mais distante. Observe-se que essas duas distâncias somam sempre

d (j, r) + f a (r, s) + d (r, s) + (1 - f) a (r, s) = d (j, r) + d (j, s) + a (r, s)

Então, segue-se que

d' (j, (r, s)) = [d (j, r) + d (j, s) + a (r, s)] / 2 (2a)

Se, por outro lado, o arco (r, s) é direccionado, então um ponto no arco (r, s) só pode ser alcançado via nó r. Consequentemente, os pontos mais distantes de (r, s) de qualquer nó são os pontos mais próximos do nó s, isto é, os pontos f para os quais f se aproxima de 1. Neste caso

d' (j, (r, s)) = d (j, r) + a (r, s) (2b)

Numere-se os arcos numa rede G de 1 a m. Denote-se por D' a matriz n × m cujo elemento j, k é a distância do nó-arco do nó j ao arco k. Observe-se que a matriz das distância do nó–arco D' pode ser calculada da matriz das distâncias entre todos os pares de nós D e o comprimento dos arcos usando as equações (2a) e (2b).

EVANS, James R.; MINIEKA, Edward - Optimization Algorithms For Networks and Graphs. 2.ª ed., Nova Iorque, Marcel Dekker, 1992.

Comments: Enviar um comentário

Links to this post:

Criar uma hiperligação



<< Home

This page is powered by Blogger. Isn't yours?