Page 25 - Telebrasil - Novembro/Dezembro 1976
P. 25
S o l u ç ã o d e u m e x e m p l o
d o p r o b l e m a d e m á x i m o t r á f e g o
n u m a d a d a r e d e t e l e f ô n i c a
A N T Ô N IO CARLOS M O U T IN H O
U M A
Diplomado em Engenharia de Telecomu Departamento de Vendas Filial Rio do
nicação pela Escola de Engonharia da Janeiro. Possui cursos de Pôs Graduação
Universidade Federal Fluminense, traba na Universidade de São Paulo — Doparta-
lhou no TELESP —Divisão de Implantação monto de Engenharia Elétrica. Atualmen
de Transmissão — Seção de PCM,Tele«u- te cursando Mestrado em Pesquise Ope
perviflão e Cabo» Coaxiais e na NEC do racional Aplicada na Universidade Fede
Brasil—Implantação PCM. ral Fluminense
No ELEBRA A.A., Eletrônico Brasileira,
exerce a função do Assessor Técnico do
Um problema usual no estudo do
dimensionamento ou redimensio
namento de uma dada rede telefônica
é de se descobrir qual o máximo
tráfego permissível nesta rede.
0 algoritmo apresentado neste artigo é
uma das aplicações do teorema do
Máximo Fluxo/Mínimo Corte: para
qualquer rede, o valor do fluxo máximo
da fonte ao sumidouro é igual à ca
pacidade do corte mínimo de todos os
cortes separando a fonte do sumi
douro.
Supomos inicialmente que o tráfego
nas rotas seja nulo. Para o caso de
tráfego existente, bastaria iniciarmos o
algoritmo a partir de qualquer figura
onde já houvesse fluxo na rede.
de tráfego. As setas indicam a direção do tráfego
Vamos imaginar que dado o diagrama
de rotas da figura 1, nosso problemc
seja descobrir qual a capacidade
máxima de tráfego que pode ser es
coada entre duas determinadas es
tações.
0 primeiro passo para a solução deste
problema será redesenhar a rede
original como mostrada na figura 2 a
fim de destacar as estações Inicial (l)e
Terminal (T) desejadas.
Aplicamos agora o "Algoritmo de
Rotulação", que consiste numa se-
qüência de rotulações (rotina A), sen
do que cada seqüência ou termina
num fluxo de maior valor (rotina B), ou
com a conclusão que o fluxo presente
Fig. 2 — Diagrama de entroncamentos rearranjado. O primeiro número nas rotas indica sua
é máximo. capacidade; o segundo, o fluxo existente
