quarta-feira, junho 07, 2006

 

Distância ponto-arco numa rede


Represente-se por d' (f – (r, s), (t, u)) a distância máxima do ponto f do arco (r, s) aos pontos do arco (t, u). Esta é a chamada distância ponto-arco.

Se o arco (r, s) não tem direcção e se (r, s) ≠ (t, u), então a rota do ponto f de (r, s) ao ponto mais distante de (t, u) deve ser ou via nó r ou via nó s. Então, segue-se que

d' (f – (r, s), (t, u)) = min {f a (r, s) + d' (r, (t, u)), (1 – f) a (r, s) + d' (s, (t, u))} (3a)

Se o arco (r, s) é direccionado e (r, s) ≠ (t, u), o primeiro termo da minimização acima pode ser eliminado e

d' (f - (r, s), (t, u)) = (1 - f) a (r, s) + ( (s, (t, u)) (3b)

Se (r, s) = (t, u) e se o arco (r, s) é direccionado, os pontos mais distantes, do arco (r, s), do ponto f de (r, s) são os pontos g tais que g se aproxima de f de valores menores que f. Assim, neste caso,

d' (f - (r, s), (r, s) = (1 - f) a (r, s) + d (s, r) (3c)

Se (r, s) = (t, u) e se o arco (r, s) não tem direcção, a distância máxima do ponto f de (r, s) para qualquer ponto g de (r, s) (onde g < f) não pode exceder

A = min {f a (r, s), [a (r, s) + d (s, r)] / 2}

O primeiro termo desta minimização leva em conta as rotas do ponto f ao ponto g limitado ao arco (r, s). O segundo termo da minimização leva em conta as rotas do ponto f de (r, s) ao ponto g de (r, s) que passam pelo nó s.

Similarmente, a distância máxima do ponto f de (r, s) a qualquer ponto g de (r, s) (onde g > f) não pode exceder

B = min {(1 - f) a (r, s), [a (r, s) + d (s, r)] / 2}

O primeiro termo da minimização precedente leva em conta as rotas do ponto f ao ponto g limitado ao arco (r, s). O segundo termo da minimização precedente leva em conta as rotas do ponto f de (r, s) ao ponto g em (r, s) que passam pelo vértice r.

Consequentemente, se o arco (r, s) não tem direcção,

d' (f - (r, s), (r, s)) = max {A, B}

ou, equivalentemente,

d' (f - (r, s), (r, s)) = max {min {f a (r, s), [a (r, s) + d (s, r)] / 2}}, min {(1 - f) a (r, s), [a (r, s) + d (r, s)] / 2}} (3d)

Quando d' (f - (r, s), (t, u)) é traçado em função de f para todos os (r, s) ≠ (t, u), a curva toma a mesma forma que nas distâncias ponto-nó mostradas na Figura 1 (Distância ponto-nó), dado que a equação (3a) tem a mesma forma que a equação (1a) e a equação (3b) tem a mesma forma que a equação (1b). Só as constantes são diferentes; as formas equacionais são as mesmas.

Por outro lado, quando d' (f - (r, s), (r, s)) é traçado em função de f para qualquer arco sem direcção (r, s), a curva toma a forma apresentada na Figura 1. Isto decorre da equação (3d).


Figura 1. Gráfico da distância ponto–arco d' (f - (r, s), (r, s))
(carregar com o cursor na figura para ver em tamanho grande)


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?