capitulo 3 - teoria dos grafos

8/17/2019 Capitulo 3 - Teoria Dos Grafos

1/65

Faculdade de Engenharia - Campus de Guaratinguetá

Pesquisa Operacional

Livro: Introdução à Pesquisa Operacional

Capítulo 3 - Teoria dos Grafos

ernando !arins " [email protected]

Departamento de Produção 1


2/65

Pesquisa Operacional - UNESP / Campus de Guaratinguetá

Sumário

• Introdução Histórico Aplicações de grafos

•Conceitos e Notação Representações de um grafoTipos de grafos

• Problemas típicos e AlgoritmosCamino !timo " Algoritmo de #$is%tra

&r'ore !tima " Algoritmo de (rus%al )lu*o +,*imo " Algoritmo de )ord " )ul%erson

2


3/65


Introdução

Histórico

Euler resolveu o problema das pontes de Königsberg do rio Pregel, em!"#, utili$ando um modelo de grafos% partir de uma das & regi'es,atravessar cada ponte uma (nica ve$ e retornar ) região de partida.

*igura . +io Pregel e suas sete pontes.3

*igura . -eonard Euler.


4/65


Introdução

*igura ". Königsberg /Kalinigrado nos tempos atuais.


5/65


Introdução

*igura &. 0odelo de 1rafo para o +io Pregel e suas sete pontes.

0odelo de grafos utili$ado por Euler para demonstrar 2ue o problema não tem solução.Para aver solução 3 necess4rio 2ue cada região tena umn(mero par de pontes associadas.

5


6/65


7/65Pesquisa Operacional - UNESP / Campus de Guaratinguetá

Introdução

. Problemas de -ocali$ação

E:istindo n cidades consumidoras do produto fabricado

por uma determinada empresa, dese;a/se saber onde seria omelor local para a instalação de uma filial desta empresa 2ueatendesse as n cidades com menor custos de distribuição do

produto.

E:istem algoritmos próprios para este problema, al3m dev4rias eur



Notação

Representações de um grafo G 1. 1=>, 5? onde%

> 9on;unto de v3rtices ou nós do grafo

5 9on;unto de arcos ou arestas do grafo

. Diagramas e tipos de grafos

8

"

a

b

c

1rafo

Aão/ orientado

1rafo Brientado

"

a

b c

d

e f

&



Notação

!. 0atri$ de ad;acCncia =grafo não/orientado? 5 =ai;?

9

∃/

∃

; nóaoi nódoaresta se,D

; nóaoi nódoaresta se,

"

D

D D

"

"

a

b

c

5



Notação

". 0atri$ de incidCncia =grafos orientados? 5 ai;F 3 a matri$ =não necessariamente 2uadrada? de

incidCncia de 1 se

= inóaoincidente3não ;arcooseD, inónoc.ega ;arcoose,/

inódosai ;arcoose,

i$a

"

a

b c

d

e f

&

10



Grafo #alorado

11

& +io de

Ganeiroão Paulo

8elo

Hori$onte

!

I

8ras


12/65



%r&ore

13

. rvore =arborescCncia?% grafo cone:o sem ciclos

a

b

d

;

g



'adeia

14

. 9adeia% se2LCncia de arcos com e:tremidade em comum

a

d

;l



'amin(o

15

". 9amino% se2LCncia de arcos com mesma orientação

a

c

f

;



'iclo e 'ircuito

16

&. 9iclo% cadeia fecada

a

dl

i b g

I. 9ircuito% camino fecadoa

b

c



Pro)lemas e *lgoritmos

17

Otimi+ação em grafos

. Determinação de rvores ótimas% 5lgoritmo de KrusMal

. Determinação de 9aminos Ntimos% 5lgoritmo de D;isMtra

". Determinação de *lu:o 04:imo% 5lgoritmo de *ord O*ulMerson



18

*lgoritmo de ,rus-al

*igura I. Gosep KrusMal.

Histórico

Em I# o matem4tico americano

Gosep KrusMal =66Q/66? propRs um algoritmo para resolução do Problema darvore 0



*lgoritmo de ,rus-al

19

eterminação de uma ár&ore m/nima num grafo G 0# *?

Para cada aresta =i, ;? e:iste um custo associado 9i;.S>S cardinalidade do con;unto de nós > n(mero de nós.

Passo . 9onsiderar o grafo trivial formado apenas pelos nós de 1

Passo . 9onstrução da rvore

5crescentar ao grafo trivial a aresta =i, ;? associada ao menor valorde custo 9i;.

+epetir o procedimento respeitando a ordem crescente de valores de9i;, desde 2ue a aresta analisada não forme ciclo com as arestas ;4incorporadas ) 4rvore.

5pós incorporar S>S / arestas⇒

PararT 5 4rvore m



$2emplo para o *lgoritmo de ,rus-al

20

Determinar uma 4rvore m


21/65



21

Passo % 1rafo trivial

21


22/65


23/65



23

rvore parcial% colocar as arestas com custo

5

8 '

D

E

23


24/65



5 seguir tem/se as arestas =b, e? e =b, f?correspondentes aos custo com valor .

5nalogamente ao caso anterior pode/se optar por2ual2uer uma elas para ser analisada primeiro.

5mbas serão incorporadas ao grafo resultante daoperação anterior, pois tamb3m não formam ciclo.

24


25/65



25

rvore parcial% colocar as arestas com custo .

5

8 '

D

E

25


26/65



26

rvore parcial% colocar a aresta com custo ".

5

8 '

D

E

"

26


27/65



27

rvore parcial% colocar as arestas com custo &.

5

8 '

D

E

"

&

&

27


28/65



28

rvore parcial% colocar uma das duas arestas com custo I, a outra

ser4 descartada.

5

8 '

D

E

"

&

&

I

28


29/65



29

9omo o n(mero de nós 3 prossegue/se neste processo at3 2ue se;am

incorporadas / arestas, sendo obtida uma 4rvore m


30/65


*lgoritmo de i4s-tra

30

*igura #. Edsger WXbe Di;Mstra.

Histórico

Em I# o cientista da computaçãoolandCs Edsger WXbe Di;Mstra concluiu odesenvolvimento do algoritmo para o

problema do camino m


31/65


*lgoritmo de i4s-tra

31

Pro)lema do 'amin(o 5timo • Determinação de caminos m


32/65


33/65


*lgoritmo de 4is-tra

33

. Uniciali$ação. 5tuali$ação dos rótulos tempor4rios". +otulação Definitiva de um nó&. Passo geral

. Uniciali$ação

+otular definitivamente o nó origem com valor .

+otular temporariamente os demais nós com valor ∞.


34/65



. 5tuali$ação dos rótulos tempor4rios

[odo nó ; ainda não rotulado definitivamente deve recebernovo valor de rótulo dado por

0in ]rótulo atual do nó ;, rótulo do nó i V ci;^,

onde,i (ltimo nó rotulado definitivamente

ci; valor associado ao arco 2ue liga os nós i e ;.

34


35/65


". +otulação definitiva9omparar os rótulos tempor4rios e escoler para serrotulado definitivamente o nó ; associado ao menorvalor. &. Passo geral

+epetir sucessivamente os passos e " at3 rotular

definitivamente o nó destino [.

O &alor da dist7ncia m/nima entre os n6s S e 8 9 o&alor do r6tulo definiti&o do n6 destino 8.


35


36/65


O)tenção dos n6s do camin(o m/nimo

\ 5 partir do nó t acar 2ual foi o nó i do passo respons4vel pelo valor de seu rótulo definitivo. upona 2ue tena sido onó M.

• 5 partir do nó M acar 2ual foi o nó i do passo respons4vel pelo valor de seu rótulo definitivo. upona 2ue tena sido onó .

• +epetir este processo at3 2ue o nó i se;a o nó origem s

• Bs nós i encontrados em cada etapa deste processo de buscaserão os nós intermedi4rios do camino m


37/65


$2emplo para 'amin(o 5timo

37

5car a distJncia m


38/65



38

:; &_ _ I_ &_ !_

+esolução completa do e:emplo de camino m


39/65



39

DistJncia malor do rótulo definitivo do nó E I sendo o nó i respons4vel 8>alor do rótulo definitivo do nó 8 sendo o nó i respons4vel

[ E 8 &


40/65


$2erc/cio

40

*

>

'

$

?

S 8

1

!

"

@

"

A

"

1

@

!

!

"

1:

5car a distJncia m


41/65

Pesquisa Operacional - UNESP / Campus de Guaratinguetá41

*nálise de Redes3 Pro)lema do ?lu2oBá2imo

*igura !. -ester +andolp *ord, Gr..

*igura Q. Delbert +aX *ulMerson..

Histórico

Em I# os matem4ticosamericanos -ester +andolp *ord

=nascido em "66!? e Delbert+aX *ulMerson =&6Q6&/66!#? propuseram em umtrabalo con;unto o algoritmo para

resolução do Problema de *lu:o04:imo.

* áli d R d P )l d ?l


42/65


*nálise de Redes3 Pro)lema do ?lu2oBá2imo

42

+ede% *ormada por duas entidades / Aós, 5rcos

Unteresse% 9omportamento da >ari4vel *lu:o

E:emplos%

*plicação N6s *rcos ?lu2oistemas de

comunicaçãoat3lites,

computadores0icro ondas,

fibra ótica0ensagens,

dados

istemasidr4ulicos

Estação de bombeamento,

reservatório

[ubos gua, g4s, petróleo

istemas detransportes

Unterseç'es,aeroportos

Estradas,rotas a3reas

>e


43/65


Problema de *lu:o 04:imo

43

Notação3 Aó fonte% Aó destino% [ *lu:o no arco =i,;?% *i; 2uantidade de produto no arco =i,;? K i; capacidade do arco =i,;? maior flu:o poss


44/65

Pesquisa Operacional - UNESP / Campus de Guaratinguetá44


e;a a rede abai:o. Dese;a/se acar o valor do flu:o m4:imo 2ue pode ser enviado do nó ao nó [, respeitando as restriç'es decapacidade nos arcos e a conservação de flu:o nos nós.

e;am K i; =ou 9i;? as restriç'es de flu:o =capacidade? no arco =i, ;?

[

**


45/65


0odelo de Programação -inear

45

0a: ` *

* V * * =? * V * [ * V * =?s. a% * V *[ * V * ="?

*[ V *[ * =&? *i; K i; =I?

• +estrição =? representa a conservação de flu:o no nó fonte .• +estriç'es =? e ="? representam a conservação de flu:o nos nósintermedi4rios e .• +estrição =&? representa a conservação de flu:o no nó destino [.• +estrição =I? restringe os flu:os a serem não/negativos erespeitarem os limites de capacidade nos arcos.


46/65



46

Dada uma rede orientada formada por arcos onde 4restriç'es de capacidade, dese;a/se enviar a maior 2uantidade=flu:o? poss


47/65



47

9onceitos 84sicos

• 5rcos )or/ard para o nó i% todo arco 2ue sai do nó i.

• 5rcos 0ac%/ard para o nó i% todo arco 2ue entra no nó i.

• 9amino entre o nó fonte e o nó destino% se2uCncia de arcos 2uese inicia no nó fonte e termina no nó destino [.

• 9iclo 3 um camino cu;os nós inicial e final são os mesmos.

• e;a A con;unto de todos os nós da rede. 7m 9orte separando afonte do destino [ 3 uma partição dos nós da rede em dois

subcon;untos denotando por a2uele 2ue cont3m o nó e por a2uele 2ue cont3m o nó [.


48/65



48

[

**

E:emplos%e;a a rede anteriormente considerada%

Aó % arcos )or/ard ]=,?,=,[?^, arcos 0ac%/ard ]=,?,=,?^

9amino% =,?,=,?,=,[?9orte% ],,^, ][^ capacidade K [ V K [

],^, ],[^ capacidade K V K V K [


49/65



49

+esultados Umportantes%

• B corte m


50/65



50

9onse2uCncias%

[odo flu:o vi4vel da fonte ao destino não pode e:ceder acapacidade de um corte 2ual2uer.

B flu:o m4:imo na rede 3 limitado pela capacidade docorte m


51/65



51

Princ


52/65



52

+otina de rotulação adotada pelo algoritmo%

7sada para acar 9*9 de para [.

.Uniciar com o nó fonte . Di$emos 2ue o nó ; pode ser rotulado se umflu:o positivo pode ser enviado a partir de para ;.

.Em geral a partir de 2ual2uer nó i pode/se rotular um nó ; se uma dascondiç'es abai:o se verifica%a?B arco 2ue conecta os nós i e ; 3 do tipo )or/ard e o flu:o *i; neste

arco =i,;? 3 menor 2ue o valor da sua capacidade K i;. b?B arco 2ue conecta os nós i e ; 3 do tipo 0ac%/ard e o flu:o *i; nestearco =;,i? 3 maior 2ue $ero.

". B processo continua at3 2ue o nó destino [ 3 rotulado. [em/se então

um 9*9.


53/65


5lgoritmo do flu:o m4:imo

53

. Uniciali$ação

Bbter um flu:o vi4vel em todos os arcos da rede. Este flu:o deve satisfa$er asrestriç'es de conservação de flu:o nos nós e as restriç'es de capacidade nosarcos. Unicialmente adotar flu:o nulo em todos os arcos.

. Procura de um camino de flu:o crescente 9*9 de para [7sar o procedimento de rotulação de nós, iniciando com o nó origem e

terminando com o nó destino [.Se não for poss/&el o)ter um '?' Parar< Cma solução 6tima foi o)tida

o flu2o atual 9 má2imo.9aso contr4rio ir a etapa ".

". 5umento no valor do flu:o entre e [9alcular o valor m4:imo de flu:o 2ue pode ser enviado pela 9*9 obtida naetapa anterior.

Aos arcos )or/ard do 9*9 aumentar o flu:o de . Aos arcos 0ac%/ard do 9*9 diminuir o flu:o de .>oltar ) etapa .


54/65


E:emplo 9ompleto

54

Determinar o flu:o m4:imo * da fonte ao destino [, na rede a seguir.

Bs n(meros ao lado dos arcos representam suas capacidades 9 i;.

Aotação% Aas pró:imas figuras os n(meros ao lado dos arcosrepresentam =*i;, 9i;?, onde *i; 3 o flu:o no arco =i, ;?. Aós rotulados serãomarcados por asteriscos-

$tapa 1 Uniciali$ação% *a$er *i; em todos as arcos.

[

**

!

Q

"


55/65


E:emplo 9ompleto

55

$tapa =*igura ? Para acar um 9*9 de para [% +otular

inicialmente . Deste nó pode/se rotular o nó pois o arco =,? 3 dotipo )or/ard e * 9 ! a seguir, do nó pode/se rotular o nó

pois o arco =,? 3 do tipo )or/ard e * 9 ". *inalmente rotula/se o nó destino [ pois o arco =,[? 3 do tipo )or/ard e *[ 9[ Q.

Usto resulta num valor de flu:o * .

*igura

_ [_

_

_

* *

=,!? =,?

=,? =,Q?

=,"?


56/65


E:emplo 9ompleto

56

Desta forma foi obtida uma 9*5 formada por arcos do tipo )or/ard ,

=,?, =,?, =,[?.

$tapa !B flu:o m4:imo neste 9*9 3 dado por min ]=! / ?, =" / ?, =Q / ?^ ".5ssim pode/se aumentar o flu:o entre e [ de ".Bs novos flu:os estão na *igura .

*igura

[

* "* "

=",!? =,?

=,?

=","?

=",Q?


57/65


E:emplo 9ompleto

57

$tapa +epetindo o processo de rotulação de nós para a configuração da

*igura obt3m/se um novo 9*9 dado por%

$tapa ! B flu:o m4:imo permitido neste 9*9 min ]=! /"?, = /?^ &.Usto aumenta o flu:o pela rede para * " V & !.5 nova configuração de flu:os fica sendo a da *igura ".

*igura "

v_ _ [_

[

* !* !

=!,!? =&,?

=,?

=","?

=",Q?


58/65


E:emplo 9ompleto

58

$tapa Aa busca de um novo 9*9, o nó não pode ser rotulado a partir do

nó pois o arco =,? 3 )or/ard e agora * 9 !. 0as um novo 9*9 pode ser obtido rotulando/se o nó e depois o nó [%

$tapa ! Aeste 9*9 o flu:o pode ser aumentado de min ]= /?, =Q /"?^ I,o 2ue resulta na configuração dada pela *igura &%

*igura &

v_ _ [_

[

* *

=!,!? =&,?

=I,?

=","?

=Q,Q?


59/65


E:emplo 9ompleto

59

$tapa % Partindo/se do nó pode/se rotular o nó , a seguir rotula/se o nó , pois

o arco =,? cont3m um flu:o positivo de " unidades e fica sendo 0ac%/ard nestenovo 9*9, finalmente a partir do nó , pelo arco =,[? rotula/se o nó destino [%

$tapa ! Aeste 9*9 pode/se aumentar o flu:o na rede de min]= /I?,",= /&?^ ", pois o arco =,? 3 0ac%/ard e pode ter o flu:o de " diminu


60/65


E:emplo 9ompleto

60

$tapa % B nó pode ser rotulado a partir do nó , mas nenum outronó pode ser rotulado a partir do nó , ou se;a, não 4 nenum 9*9adicional.

-ogo obteve/se o flu:o m4:imo de para [ dado por I unidades deflu:o.

Bbservação% Pode/se usar o teorema de *ord O *ulMerson para provar

2ue o flu:o m4:imo 3 de fato I. >e;a a *igura #.


61/65


E:emplo 9ompleto

61

9onsidere o corte 2ue separa os nós rotulados dos não rotulados na(ltima etapa , ele 3 formado pelos arcos =,?,=,? e =,[?, tendo

capacidade I e separa o nó do nó [.Pelo [eorema de * O * o flu:o não pode e:ceder a capacidade denenum corte 2ue separe o nó do nó [, logo o corte em 2uestão 3 ocorte m


62/65


E:tens'es para o problema de *lu:o04:imo

62

+ede não/orientada% considere a rede urbana abai:o%

0a:imi$ar o flu:o de tr4fego de at3 [.

[

"

&

&

"

I

"

I

I

I

"

E:tens'es para o problema de *lu:o


63/65



63

5plicar o algoritmo apresentado e acar *lu:o 04:imo.e arco =i,;? não 3 direcionado e f i; f ;i flu:o =f i; f ;i? ser4enviado de i para ;.

=5de2uar mão de trJnsito no arco i ;?

[rabalar com modelo e2uivalente de redes%

[

"

&

&

"

I

"

I

I

I

"

I I



64/65



64

Aó 5 *onte com oferta produto =Bferta [otal &? Aó D *onte com oferta produto Aó E Destino com demanda produto I =Demanda [otal "I? Aó H Destino com demanda produto

0(ltiplas fontes e m(ltiplos destinos%

CC C

I

I

I

I

I I

I

5

8

9

D

E

*

1

H

9apacidadedo arco



65/65


C

C

C

C

C

CC

C

CC

I

I I

I

II

I I

f fict

capitulo 3 - teoria dos grafos

Documents