Page 26 - Telebrasil - Novembro/Dezembro 1976

As estações são consideradas em 3 es­

tados:

— não-rotulada

— rotulada e explorada

— rotulada e não-explorada

ROTINA A

(Processo de Rotulação): Inicialmente,

a Estação Inicial I recebe o rótulo (- , l

(D = 0 0 ) = ( - , 0 0 ) (A Estação Inicial,

agora está rotulada e não-explorada;

todas as outras estações estão não-

rotuladas). Selecionamos qualquer es­

tação x não-explorada. Suponhamos

que ela esteja rotulada (z ± , £ (X)).

Para todas as estações y que estejam

não-rotuladas e tais que f (x,y) < c(x,y)

(o fluxo de x para y é menor do que sua

capacidade de fluxo), designaremos o

rótulo (x+ , £ (y) ), onde: Fig. 3 — Computação da Rotulação. As rotas pontilhadas indicam o caminho da rotulação

£ (y) = min [ t (x),c(x,y) - f(x,y) 1

(Esta estação y está agora rotulada e

não-explorada). Para toda estação y tal

que, f (y,x) > 0, atribuiremos o rótulo

(x- , £ (y) ), onde:

£ (y) = min l £ (x), f(y,x) 1

Repetiremos o processo até que a Es-

:ação Terminal T seja atingida e então

entraremos na rotina B. Caso a Es­

tação Terminal não seja atingida, o al­

garismo terminou (o tráfego presente é

d máximo possível para esta rede).

ROTINA B

(Mudança de Fluxo): O rótulo da Es­

tação Terminal é do tipo (y+ , L (T)).

Substituímos f(y,T) por f(y,T) + 1 (T).

Se T é rotulada (V , c (T)), substi­

tuímos f(T, y) por f(T,y) - c (T).

A seqüência de computação realizada

neste exemplo está indicada nas fi­

guras de 3 a 10. (l * 6 0 'j

Na figura 10, são mostradas as rotas

que estariam operando com máxima

utilização, onde pode ser observado o

grau de saturação máxima deste sis­

tema telefônico.

O presente algoritmo pode ser aplicado

em muitos outros tipos de redes e é

uma excelente ferramenta para uma

primeira aproximação da solução de

problemas de fluxo em redes mais

complexas.

Bibliografia:

L.R. Ford, Jr., and D.R. Fulkerson,

Flows in Networks. Princeton Univer­

sity Press.