INSTITUTO SUPERIOR TÉCNICO - Autenticação · 3º - Diminuir de c a capacidade de fluxo em cada arco do caminho no sentido considerado e aumentar de c a capacidade dos arcos no

INSTITUTO SUPERIOR TÉCNICO

DEPARTAMENTO DE ENGENHARIA CIVIL

INVESTIGAÇÃO OPERACIONAL I

OPTIMIZAÇÃO EM REDES E GRAFOS

Algoritmos para os problemas de

- Fluxo máximo

- Caminho mais curto

- Árvore de ligações mínima

RUI MOURA DA SILVA

Março de 1995

OPTIMIZAÇÃO EM REDE E GRAFOS

2

PREÂMBULO

Apresentam-se neste texto, algoritmos para a resolução de três problemas clássicos de

optimização em redes e grafos: fluxo máximo (Ford-Fulkerson), caminho mais curto

(Dijkstra) e árvore de ligações mínima (Kruskal).

Entende-se por grafo uma representação esquemática de um conjunto de pontos (a que

se dá o nome de nós ou vértices) ligados por linhas (arcos ou arestas). Os nós, pontos

no espaço ou no tempo, são representados por circulos; os arcos representam ligações

entre nós, e aos quais podem estar associados, por exemplo, distâncias, tempos ou

custos de deslocação entre os nós, e podem ser orientados - quando a ligação entre os

nós só é possível num sentido (sendo representado por uma seta indicando aquele

sentido), - ou não orientados - quando a ligação entre os nós pode ser em qualquer dos

dois sentidos (caso em se desenha apenas uma linha).

Em rigor, a denominação de grafo é dada quando os arcos são não orientados e a de

rede quando os arcos são orientados. No entanto, hoje em dia, estas duas

denominações tendem a confundir-se, pelo que no texto que se apresenta não se fará

distinção entre elas.

Há variadíssimos problemas de grande relevância prática que são formuláveis em

termos de uma rede ou grafo, sendo o desenvolvimento de algoritmos de optimização

para a resolução desses problemas, uma das áreas de grande actividade da

Investigação Operacional.

De entre estes, seleccionaram-se os três algoritmos que se apresentam de seguida. O

problema do fluxo máximo, consiste na determinação do número máximo de unidades

de fluxo que é possível enviar através dum grafo, desde o nó origem até ao nó destino,

quando os arcos tem capacidade limitada. O algoritmo para a resolução deste

problema é apresentado no capítulo 1.


3

Como o nome sugere, o problema do caminho mais curto, surge quando definido um

nó origem e um de destino, se pretende determinar o caminho que permite ir do

primeiro para o segundo nó percorrendo a menor distância. No capítulo 2, é

apresentado o respectivo algoritmo resolutivo.

O capítulo 3 é dedicado ao problema da árvore de ligações mínima, que consiste na

identificação do conjunto de arcos que permitem interligar todos os nós de um grafo

com uma ligação de comprimento mínimo.


4

Indice

PREÂMBULO..............................................................................................................2

INDICE .........................................................................................................................4

1 - O PROBLEMA DO FLUXO MÁXIMO ..............................................................5

2 - O PROBLEMA DO CAMINHO MAIS CURTO..............................................11

3 - O PROBLEMA DA ÁRVORE DE LIGAÇÕES MÍNIMA..............................19

BIBLIOGRAFIA........................................................................................................25


5

1 - O PROBLEMA DO FLUXO MÁXIMO

De um modo geral, pode dizer-se que um fluxo corresponde ao envio de entidades de

um lugar para outro; por exemplo, o envio de produtos acabados do produtor para o

distribuidor, as deslocações das pessoas das suas casas para os locais de trabalho, a

expedição de cartas desde a estação de correios até aos seus destinatários, etc.

Em termos de um grafo, o fluxo é o envio de entidades de um nó (origem) até outro nó

(destino) percorrendo alguns dos arcos da rede de que aqueles nós fazem parte.

Define-se capacidade de um arco orientado (i!j) como o número máximo de

unidades de fluxo que se pode enviar do nó i para o nó j. Naturalmente que o fluxo

que pode percorrer um arco variará entre zero e a sua capacidade.

Graficamente, a capacidade de um arco representa-se junto ao nó a partir do qual essa

capacidade existe. Assim, no caso da figura 1.1, verifica-se que existe uma capacidade

de 9 unidades de fluxo do nó 1 para o nó 3 e de 1 unidade de fluxo do nó 3 para o 1.

9 11 3

Figura 1.1 - Capacidade de um arco

O fluxo máximo que se pretende determinar, será, portanto, o número máximo de

unidades de fluxo que é possível enviar através da rede desde o nó origem até ao nó

destino (admite-se que há conservação de fluxo, ou seja, que o fluxo que parte da

origem chega totalmente ao destino não havendo, portanto, perdas pelo caminho).


6

Considere-se a rede representada na figura 1.2

2 2 32

15 8

2 37 9 1 1 4

ORIGE M 1 3 3 7 DE S TINO5 2 2 1

22 6 9

3 20 4 4

Figura 1.2 - Rede

O problema do fluxo máximo pode resolver-se por Programação Linear, mas o

algoritmo, devido a Ford-Fulkerson, que se vai descrever é muito mais expedito.

Os passos de cada iteração do algoritmo podem ser resumidos do seguinte modo:

1º - Escolhe-se um caminho qualquer desde a origem até ao destino, mas em que

os arcos orientados que o constituiem tenham capacidade positiva (>0).

2º - Procurar nesse caminho o arco orientado com menor capacidade, c,

3º - Diminuir de c a capacidade de fluxo em cada arco do caminho no sentido

considerado e aumentar de c a capacidade dos arcos no sentido inverso.

Regressar ao 1º passo. Se já não existir nenhum caminho em que todos os

arcos tenham capacidade positiva, tal significa que já se determinou o fluxo

máximo.

Vamos aplicar este algoritmo à rede dada.

1º passo - Considere-se, por exemplo, o caminho que passa pelos nós 1, 2, 5 e 7.

2º passo - Verifica-se que a menor capacidade destes arcos orientados, no sentido

de 1 para 7, é de 3 = Min(7,3,8), ver fig 1.2.

3º passo - Subtrai-se este valor de 3 a 7 (= 4 no arco 1!2), a 3 (=0 no arco 2!5)

e a 8 (= 5 no arco 5!7); soma-se o mesmo valor a 2 (= 5 no arco 2!1), a 1 (=

4 no arco 5!2) e a 4 (= 7 no arco 7!5) e actualizam-se os valores das

capacidades.


7

Sobre as setas de entrada, junto ao nó 1, e de saída, junto ao nó 7, escreve-se o valor

do fluxo já transportado de 1 para 7 (fig 1.3).

5 2 02

45 5

2 33 4 9 1 1 7 3

1 3 3 75 2 2 1

22 6 9

3 20 4 4

Figura 1.3 - 1ª iteração

Admita-se que na iteração seguinte se escolhia o caminho 1, 4, 6 e 7.

A menor capacidade destes arcos orientados seria 4 = Min(5,4,9), ver figura 1.3, valor

que se subtraía e somava às capacidades dos arcos considerados conforme já descrito.

Às 3 unidades de fluxo que já se tinham transportado na 1ª iteração somavam-se as 4

de agora, inscrevendo-se o resultado nas setas de entrada e saída (fig. 1.4).

5 2 02

45 5

2 37 4 9 1 1 7 7

1 3 3 71 2 2 5

22 6 5

3 64 4 0



8

Suponha-se que na 3ª iteração se escolhia o caminho 1, 3, 5 e 7. A menor capacidade

seria agora 3 = Min(9,3,5) e procedia-se como anteriormente (fig 1.5).

5 2 02

45 2

5 310 4 6 4 1 10 10

1 3 0 71 2 2 5

22 6 5

3 64 4 0


Na 4ª iteração poderia escolher-se o caminho 1, 3, 6 e 7, em que a menor capacidade é

de 2 = Min(6,2,5), actualizando-se os valores das capacidades dos arcos orientados e

do fluxo de atravessamento (fig 1.6)

5 2 02

45 2

5 312 4 4 6 1 10 12

1 3 0 71 2 0 7

24 6 3

3 64 4 0


Como se pode verificar na figura 1.6, já não existe nenhum caminho com capacidade

positiva. Com efeito, os arcos 2!5, 3!5, 3!6 e 4!6 têm todos capacidade nula,

pelo que não é possível constituir qualquer caminho de 1 a 7 com capacidade maior

que zero.

Está, portanto, encontrado o fluxo máximo possível de deslocar desde o nó origem até

ao nó destino - 12 unidades de fluxo.


9

Para se saber em cada arco orientado qual o valor e sentido do fluxo que o percorre,

tem de se subtrair à capacidade inicial (fig 1.2) a capacidade final (fig 1.6).

Se o resultado for positivo, tal significa que o fluxo parte do nó que se está a

considerar; se for negativo é por que chega a esse nó.

Assim, para o arco 1!2, a capacidade inicial era de 7 (fig 1.2) e a final de 4 (fig 1.6),

pelo que 7-4=3 >0, logo o fluxo é de 1 para 2 (parte de 1) e é de 3 unidades de fluxo.

Se se analizasse o arco 2!1, simétrico do anterior, teríamos 2-5= -3 <0 e, portanto, o

fluxo ia de 1 para 2 (chega a 2) de 3 unidades de fluxo, como já se tinha verificado.

Fazendo, agora, a análise para toda a rede, verifica-se que os fluxos fluíam como

indicado na figura 1.7. De notar que se o fluxo máximo é bem definido e igual a 12, o

modo como ele percorre a rede, variará de acordo com os caminhos escolhidos nas

iterações, havendo, normalmente, mais do que um modo de o fazer.

23

35 6

312 5 12

1 3 72

6 64

4 4

Figura 1.7 - Fluxo nos arcos

Apesar deste algoritmo ser bastante expedito, se apenas se quiser conhecer o valor do

fluxo máximo do nó origem para o nó destino e, nomeadamente, se se tratar de uma

rede de grandes dimensões, é possível resolver este problema recorrendo ao Teorema

do Fluxo Máximo :

- para toda a rede com uma só origem e um só destino o fluxo máximo

é igual ao valor mínimo de corte de entre todos os cortes possíveis da

rede.


10

Um corte é um conjunto de arcos orientados contendo, pelo menos, um ramo de cada

caminho da origem ao destino. O valor de corte é a soma das capacidades de fluxo de

todos os ramos do corte, no sentido da orientação definida pelo corte.

Na figura 1.8 apresentam-se alguns dos cortes da rede dada (não se traçaram os

restantes de modo a que a figura não ficasse incompreensível), sendo um deles o corte

que indica o fluxo máximo da rede, ou seja o que tem menor valor de corte.

2 2 32

7+9+5 = 21 15 8

2 37 9 1 1 4

1 3 3 75 2 2 1

22 6 9

3 2 8+9 = 170 4 4

7+1+3+2+2+5 = 203+3 +2 +4 = 12

Figura 1.8 - Cortes

Observe-se que este corte secciona precisamente os arcos orientados que na solução

final tem capacidade nula, ver figura 1.6, o que indica que se se quiser aumentar o

fluxo máximo desta rede deverá ser precisamente sobre estes arcos que se deve actuar.


11

2 - O PROBLEMA DO CAMINHO MAIS CURTO

Neste problema procura determinar-se o conjunto de arcos de uma rede que

constituem o caminho mais curto, de entre todos os caminhos possíveis, do nó origem

ao nó destino.

O algoritmo que vai permitir determinar o caminho mais curto, devido a Dijkstra, é

aplicável a distâncias generalizadas, "distâncias" que podem ser expressas em

unidades de comprimento, de tempo, monetárias, etc, . Assim pode obter-se, por

exemplo, o caminho mais rápido (desde que os arcos passem a representar os tempos

gastos para os percorrer), o mais económico (com os arcos a representar os

correspondentes custos), etc.

Considere-se a matriz origem-destino (O/D) apresentada na fig 2.1 :

O\D A B C D E F G H I

A - 3 5

B 3 - 7 8

C 5 7 - 4 2

D 8 4 - 3 3 7

E 2 3 - 4 2

F 3 - 5 6

G 4 5 - 3 8

H 2 3 - 7

I 6 8 7 -

Fig 2.1 - Matriz O/D

Numa matriz O/D, a 1ª coluna representa os nós origem, a 1ª linha os nós destino e os

números que aparecem no interior da matriz indicam a distância entre cada par de nós

i e j (se existir entre eles uma ligação directa, ou seja, se for possível ir do nó i ao nó j

sem ter de passar por nenhum outro); se não existir nenhum número na casa (i,j) tal

significa que a ligação entre esses nós só se pode fazer passando por outro(s) nó(s).


12

Na matriz O/D dada, pode ler-se, por exemplo, que existe uma ligação directa entre C

(origem) e E (destino) cuja distância é de 2, o que já não acontece, por exemplo, entre

H (origem) e D (destino) que não têm ligação directa; pode ainda ler-se que é possível

o trajecto directo entre D (origem) e G (destino), mas que de G para D já não

(corresponde ao que ocorre em redes urbanas em que existem ruas de sentido único).

Representando graficamente a rede descrita na matriz O/D (fig 2.2)

F3

8 6B D ´ 5

3 74 8

A ´ 7 ´ 3 G I5 4

C E ´ 3 ´ 72 2

H

Fig 2.2 - Rede

O algoritmo que se vai descrever consiste em, a partir do nó origem (ou de partida), ir

em cada iteração determinando o nó que está a menor distância do nó origem (que

passara a ser um nó original) até se alcançar o nó destino.

Por outras palavras, as distânciais dos nós originais, que forem sendo determinados,

ao nó origem, formarão uma sucessão não decrescente (em cada iteração a distância

ao nó origem é superior ou igual à obtida na iteração anterior).

Quando um nó passa a ser um nó original, todas as ligações directas que o têm como

destino deixam de ter utilidade e são eliminadas.

Passemos, agora, à descrição pormenorizada deste algoritmo e utilizando a matriz O/D

dada, vamos determinar o caminho mais curto desde o nó A até ao nó F.

1ª iteração - Dado que o nó A é o nó origem, será por definição, o primeiro nó

original, pelo que se podem, desde logo, eliminar todas as ligações que o têm por

destino (riscando os números contidos nas casas B!A e C!A) e inscrevendo na

coluna da distâncias a A (Dist a A) um zero (≡ à distância de A a A) (fig 2.3).


13

O\D A B C D E F G H I Dista A

Mindist.

A - 3 5 0

B /3 - 7 8

C /5 7 - 4 2

D 8 4 - 3 3 7

E 2 3 - 4 2

F 3 - 5 6

G 4 5 - 3 8

H 2 3 - 7

I 6 8 7 -

Fig 2.3 - 1ª iteração

2ª iteração - A partir do nó A, determina-se qual o nó original seguinte, que, como se

pode verificar na matriz O/D, é o nó B a uma distância de 3, marcando-se com um

circulo a posição correspondente ao arco que estabeleceu esta ligação (A!B).

Se o nó B passou a ser nó original, eliminam-se todas as ligações que o têm como

destino (C!B e D!B) e inscreve-se na coluna das distâncias a A o valor 3

(correspondente à mínima distância de B a A) (fig 2.4).


Mindist.

A - " 5 0 3

B /3 - 7 8 3

C /5 /7 - 4 2

D /8 4 - 3 3 7

E 2 3 - 4 2

F 3 - 5 6

G 4 5 - 3 8

H 2 3 - 7

I 6 8 7 -



14

3ª iteração - A partir dos nós originais - A e B -, vão determinar-se as mínimas

distâncias a A:

- de A será C a uma distância 5 (0+5), (A!C)

- de B será C a uma distância de 10 (3+7) (A!B + B!C)

O novo nó original será, pois, C, eliminando-se todas as ligações com destino a C,

marcando com um circulo o arco que estabeleceu a ligação - A!C - e inscrevendo-se

na coluna das distâncias a A o valor 5 (menor valor encontrado) (fig 2.5).


Mindist.

A - " # 0 5

B /3 - /7 8 3 10

C /5 /7 - 4 2 5

D /8 /4 - 3 3 7

E /2 3 - 4 2

F 3 - 5 6

G 4 5 - 3 8

H 2 3 - 7

I 6 8 7 -


Este processo iterativo vai-se repetindo até se atingir o nó F, destino final do caminho

mais curto a determinar.

Assim, - 4ª iteração:

- a partir de A já não se pode atingir directamente mais nenhum nó,

- a partir de B é o nó D a uma distância de 11 (3+8),

- a partir de C é o nó E a uma distância de 7 (5+2),

pelo que o novo original será o nó E a uma distância de 7 de A, valor que se inscreve

na coluna respectiva, marcando o arco - C!E - e eliminando-se todas as ligações com

destino a E (fig 2.6).


15


Mindist.

A - " # 0 -

B /3 - /7 8 3 11

C /5 /7 - 4 $ 5 7

D /8 /4 - /3 3 7

E /2 3 - 4 2 7

F 3 - 5 6

G /4 5 - 3 8

H /2 3 - 7

I 6 8 7 -


Apresentam-se a seguir os quadros que se obteriam nas iterações seguintes no

prosseguimento do algoritmo.

Na seguinte (5ª), surge um igualdade a 9 entre atingir o nó D a partir de C e atingir H a

partir de E. Dado que são nós distintos, é indiferente qual o que se escolhe; se fosse o

mesmo nó, tal significava que havia dois caminhos mais curtos distintos para chegar a

esse nó a partir de A.

Admitamos que se escolheu D, escolha arbitrária, pois a solução final, caminho mais

curto e correspondente distância, será sempre a mesma (fig 2.7).


Mindist.

A - " # 0 -

B /3 - /7 /8 3 11

C /5 /7 - % $ 5 9

D /8 /4 - /3 3 7 9

E /2 /3 - 4 2 7 9

F /3 - 5 6

G /4 5 - 3 8

H /2 3 - 7

I 6 8 7 -



16

Na iteração seguinte (6ª) o novo nó original será, então, o nó H (fig 2.8)


Mindist.

A - " # 0 -

B /3 - /7 /8 3 -

C /5 /7 - % $ 5 -

D /8 /4 - /3 3 7 9 12

E /2 /3 - 4 $ 7 9

F /3 - 5 6

G /4 5 - /3 8

H /2 3 - 7 9

I 6 8 /7 -


Nesta iteração (7ª) é G o novo nó original (fig 2.9)


Mindist.

A - " # 0 -

B /3 - /7 /8 3 -

C /5 /7 - % $ 5 -

D /8 /4 - /3 3 /7 9 12

E /2 /3 - % $ 7 11

F /3 - /5 6

G /4 5 - /3 8 11

H /2 /3 - 7 9 12

I 6 /8 /7 -



17

Finalmente na 8ª iteração atinge-se o nó F (fig 2.10)


Mindist.

A - " # 0 -

B /3 - /7 /8 3 -

C /5 /7 - % $ 5 -

D /8 /2 - /3 " /7 9 12

E /2 /3 - % $ 7 -

F /3 - /5 6 12

G /4 /5 - /3 8 11 16

H /2 /3 - 7 9 16

I /6 /8 /7 -


O conjunto dos arcos que fazem parte do caminho mais curto vai ser reconstituído do

fim para o princípio utilizando o quadro final.

Entrando na coluna do nó F (destino) procura-se o circulo que representa o arco

utilizado para chegar a este nó e verifica-se que esse arco tem origem em D (linha

onde está o circulo). Passando para a coluna do nó D, constata-se que se chegou até

ele a partir do nó C. Prosseguindo o mesmo processo, verifica-se que se atingiu o nó C

a partir de A, que é o nó origem.

Conclui-se, portanto, que o caminho mais curto desde o nó A até ao nó F passa pelos

nós

A - C - D - F

com uma distância de 12 (5+4+3) conforme se verifica no último quadro na coluna

das distâncias a A.

De notar, que ao determinar o caminho mais curto de A a F, obtiveram-se, também, as

mínimas distâncias de A a todos os nós originais. Por exemplo, de A a G a mínima

distância é 11 e o caminho constituído pelo conjunto de arcos orientados - A!C!E!

G.

Por outro lado, verifica-se que o nó I não chegou a ser atingido, o que revela que a sua

distância a A será maior do que 12 (quanto muito podia ser igual a 12, o que não

acontece no caso presente em que seria de 16 a partir do nó H).


18

O grafo do caminho mais curto entre A e F é o seguinte :

F3

B D

4A G I

5

C E

H

Fig 2.11 - Grafo do caminho mais curto de A a F


19

3 - O PROBLEMA DA ÁRVORE DE LIGAÇÕES MÍNIMA

Neste problema procura determinar-se o conjunto de arcos que permitem interligar

todos os nós de um grafo de modo a que o seu comprimento (somatório dos

comprimentos dos arcos que o constituiem) seja mínimo.

Esta interligação significa que de qualquer nó i se possa chegar (directa ou

indirectamente) a qualquer outro nó j e vice-versa, o que implica que as ligações

directas entre nós têm de ter sempre os 2 sentidos e a mesma "distância" (se existe

uma ligação directa de k para m com uma "distância" d, tem de existir, também, uma

ligação directa de m para k com o mesma "distância").

Caso haja uma ligação directa e não exista a sua simétrica, a primeira deve ser

eliminada; no caso de existirem as duas ligações mas com "distâncias" diferentes,

esses 2 nós não devem ser considerados na determinação inicial da árvore de ligações

mínimas, deixando para uma segunda fase a sua eventual introdução.

Tal como no problema do caminho mais curto, a palavra "distância" deve ser

entendida como distância generalizada, ou seja, pode estar expressa em unidades de

comprimento, de tempo, monetárias, etc.

A árvore de ligações mínima é uma árvore arborescente, isto é, a sua representação

gráfica tem a forma de uma árvore "aberta", isto é, nunca forma polígonos fechados.

Da definição da árvore de ligações mínima conclui-se, imediatamente, que ela não tem

nem origem nem destino (qualquer nó é simultaneamente origem e destino

relativamente a todos os outros) e será constituída maioritariamente pelos arcos de

menor comprimento, dado que se pretende que o somatório do comprimento dos arcos

que dela farão parte seja o menor possível.

O algoritmo que se vai descrever, devido a Kruskal, em cada iteração vai escolher, a

partir dos arcos de menor comprimento (que previamente se ordenaram por ordem

crescente), quais os nós que podem ser incluídos na árvore de modo a que ela nunca

forme polígonos.


20

Considere-se a matriz origem-destino (O/D) que se utilizou para o problema do

caminho mais curto e que se apresenta, de novo, na fig 3.1:

O\D A B C D E F G H I

A - 3 5

B 3 - 7 8

C 5 7 - 4 2

D 8 4 - 3 3 7

E 2 3 - 4 2

F 3 - 5 6

G 4 5 - 3 8

H 2 3 - 7

I 6 8 7 -

Fig 3.1 - Matriz O/D

Como se disse, há que, em primeiro lugar, eliminar as ligações directas para as quais

não exista ligação directa inversa ou existindo, não tenha o mesmo comprimento. No

caso presente elimina-se a ligação D!G, visto não existir a ligação G!D.

A seguir, ordenam-se os arcos por ordem crescente do seu comprimento. Recorde-se,

que quando se escreve, por exemplo, CE - 2, esta notação indica a existência das duas

ligações directas (C!E e E!C) com um comprimento igual a 2.

CE - 2 AC - 5

EH - 2 FG - 5

AB - 3 FI - 6

DE - 3 BC - 7

DF - 3 HI - 7

GH - 3 BD - 8

CD - 4 GI - 8

EG - 4


21

1ª iteração - Dado que a árvore de ligações mínima não tem nó origem nem nó

destino, pode começar-se por qualquer nó que a solução final não se altera.

Considere-se, então, o primeiro arco da lista ordenada- CE - o que implica que esta

ligação, por ter um dos menores comprimentos, faz parte da árvore de ligações

mínima - e marca-se (&) esta ligação na lista

CE - 2 & AC - 5 C - E

EH - 2 FG - 5

AB - 3 FI - 6

DE - 3 BC - 7

DF - 3 HI - 7

GH - 3 BD - 8

CD - 4 GI - 8

EG - 4

2ª iteração - A ligação seguinte da lista é EH que conecta com a anterior, pelo que se

faz essa conexão e marca-se a ligação na lista.

CE - 2 & AC - 5 C - E - H

EH - 2 & FG - 5

AB - 3 FI - 6

DE - 3 BC - 7

DF - 3 HI - 7

GH - 3 BD - 8

CD - 4 GI - 8

EG - 4

3ª iteração - Prosseguindo o varrimento da lista, a ligação seguinte é AB que não

conexa com a árvore que se está a traçar, pelo que se desenha essa ligação ao lado;

como anteriormente, marca-se essa ligação na lista.


22

A posição e a forma como esta ligação é colocada tem apenas a ver com uma maior

facilidade de exposição e pelas razões que a seguir se verão.

CE -2 & AC - 5 B - A C - E - H

EH -2 & FG - 5

AB -3 & FI - 6

DE - 3 BC - 7

DF - 3 HI - 7

GH - 3 BD - 8

CD - 4 GI - 8

EG - 4

4ª iteração - A ligação seguinte é DE ; visto que o nó E já tem duas ligações definidas,

desenha-se uma terceira.

CE -2 & AC - 5 B - A C - E - H

EH -2 & FG - 5 |

AB -3 & FI - 6 D

DE - 3& BC - 7

DF - 3 HI - 7

GH - 3 BD - 8

CD - 4 GI - 8

EG - 4

5ª iteração - Segue-se DF

CE -2 & AC - 5 B - A C - E - H

EH -2 & FG - 5 |

AB -3 & FI - 6 D

DE - 3 & BC - 7 |

DF - 3 & HI - 7 F

GH - 3 BD - 8

CD - 4 GI - 8

EG - 4


23

6ª iteração - Através da ligação GH o nó G fica conectado com a árvore que vimos

determinando.

CE -2 & AC - 5 B - A C - E - H - G

EH -2 & FG - 5 |

AB -3 & FI - 6 D

DE - 3 & BC - 7 |

DF - 3 & HI - 7 F

GH - 3 & BD - 8

CD - 4 GI - 8

EG - 4

7ª iteração - A ligação seguinte da lista é CD, mas esta ligação não pode ser

considerada porque formava uma polígono fechado (triângulo C-D-E) e como se

disse, a árvore de ligações mínima é arborescente.

Passando à ligação seguinte EG, verifica-se que, pela mesma razão, também não pode

ser considerada (circuito fechado E-G-H).

Com a ligação seguinte da lista, AC, vai fazer-se a conexão entre as duas partes da

árvore já desenhadas (tornam-se, agora, claras as razões invocadas na 3ª iteração).

CE -2 & AC - 5 & B - A - C - E - H - G

EH -2 & FG - 5 |

AB -3 & FI - 6 D

DE - 3 & BC - 7 |

DF - 3 & HI - 7 F

GH - 3 & BD - 8

CD - 4 GI - 8

EG - 4


24

8ª iteração - Pelas razões já indicadas, a ligação FG não pode ser considerada

(formava-se o pentagono D-E-H-G-F), passando-se, portanto, para a ligação seguinte

FI, que vai permitir que os 9 nós considerados (A, B, C, D, E, F, G, H e I) fiquem

todos interligados, ou seja, já está determinada a árvore de ligações mínima

pretendida.

CE -2 & AC - 5 & B - A - C - E - H - G

EH -2 & FG - 5 |

AB -3 & FI - 6 & D

DE - 3 & BC - 7 |

DF - 3 & HI - 7 F

GH - 3 & BD - 8 |

CD - 4 GI - 8 I

EG - 4

Definida a árvore de ligações mínima, há que determinar o seu comprimento, para o

que basta somar os comprimentos dos arcos marcados:

2 + 2 + 3 + 3 + 3 + 3 + 5 + 6 = 27

O grafo correspondente à árvore de ligações mínima é o que se apresenta a seguir :

F3

6B D

3

A ´ 3 G I5

C E ´ 32 2

H

Fig 3.2 - Grafo da árvore de ligações mínima


25

BIBLIOGRAFIA

BUDNICK, FRANK S., DENNIS McLEAEY e RICHARD MOJENA

Principles of Operations Research for Management

Irwin, 1988

HILLIER, FREDERICK S. e GERALD J. LIEBERMAN

Introduction to Operations Research

McGraw-Hill, 1990

MINIEKA, EDWARD

Optimization Algorithms for Networks and Graphs

Marcel Dekker, 1978

ZÚQUETE, EDUARDO

Teoria dos grafos

1982

Documents

INSTITUTO SUPERIOR TÉCNICO - Autenticação · 3º - Diminuir de c a capacidade de fluxo em cada arco do caminho no sentido considerado e aumentar de c a capacidade dos arcos no