BC1429 — Teoria Dos Grafos

7/23/2019 BC1429 Teoria Dos Grafos

1/40

BC1429 TEORIA DOS GRAFOS

JAIR DONADELLI

Sumrio

SumrioAvisoSmbolos1. Grafosdefini!es ini"iaisE#er""ios 1.1. GrauE#er""ios$. Sub%rafos $.1. Sub%rafo indu&ido 'or um sub"on(un)o de v*r)i"es $.$. Sub%rafo indu&ido 'or um sub"on(un)o de ares)as $.+. E#er""ios+. ,li-ue "on(un)o inde'enden)e %rafo bi'ar)ido e "or)e +.1. E#er""ios/. Isomorfismo

/.1. E#er""ios0. Ou)ras no!es de %rafos 0.1. E#er""ios. Re'resen)a2o "om'u)a"ional .1. 3a)ri& de ad(a"4n"ias de G .$. Lis)a de ad(a"4n"ias de G .+. ,om'le#idade de al%ori)mos em %rafosE#er""ios5. 6er"ursos em %rafos 5.1. 6er"urso %en*ri"o 5.$. E#er""ios7. Al%ori)mos de bus"a 7.1. 8us"a em Lar%ura

7.$. 8us"a em 6rofundidade 7.+. E#er""ios9. ,amin:os e ,ir"ui)os 9.1. E#er""ios1;. ,amin:os mnimos em %rafos "om 'esos nas ares)as 1;.1. E#er""ios11. Al%ori)mo de Di(


2/40

$$.$. >lu#o em redesE#er""ios

Aviso

Esse )e#)o "on)*m :'erlin


3/40

'assam a ser referidos "omo +QG e EQG res'e")ivamen)e. Assim se G M QX,Y en)2o V QG MX eEQG M Y .

6ara um %rafo G -ual-uer ":amamos KV QGK de or!"m de G e ":amamos KV QGK KEQGK de )ama#o de G.

Tm e#'oen)e em G -uando G * um %rafo deno)a a ordem de G assim -uando -ueremos ressal)ar -ue G * um %rafo de ordem n 'ara al%umn es"revemos G#.

,:amamos G;M Q, de 'rao va/io e )odo %rafo de ordem 1 de 'rao )rivial.

E-"r&&ios

Exerccio 1.Tm -umi"o dese(a embar"ar os 'rodu)osA,B,C,,E,!,X usando o menor nHmero de "ai#as. Al%uns 'rodu)os n2o 'odem ser"olo"ados numa mesma "ai#a 'or-ue rea%em. Os 'rodu)osA,B,C,X rea%em doisadoisA rea%e "om! e "om e vi"eversaE )amb*m rea%e"om! e "om e vi"eversa. Des"reva o %rafo -ue modela essa si)ua2o mos)re um dia%rama desse %rafo e use esse %rafo 'ara des"obrir o menornHmero de "ai#as ne"essrias 'ara embar"ar os 'rodu)os "om se%urana.

Exerccio $.Adal)ina es'erava / ami%as 8randelina ,lodina De(aina e Edina 'ara um lan":e em sua "asa. En-uan)o es'erava 're'arou aslan":es 8auru 3is)o -uen)e 3is)o frio e Vsalada. 8randelina %os)a de 3is)o frio e de Vsalada ,lodina de 8auru e Vsalada De(aina %os)a de3is)o -uen)e e 3is)o frio Edina %os)a de de 8auru e 3is)o -uen)e. Des"reva o %rafo -ue modela essa si)ua2o mos)re um dia%rama desse %rafoe use esse %rafo 'ara des"obrir se * 'ossvel -ue "ada ami%a de Adal)ina )en:a o lan":e -ue %os)a.

Exerccio +.6ara )odo n -ual * o nHmero m#imo de ares)as -ue 'ode )er um %rafo "om n v*r)i"esW

Exerccio /.O &om0l"m"#)o de um %rafo G deno)ado 'or G * o %rafo -ue )em o mesmo "on(un)o de v*r)i"es de Ge dois v*r)i"es formam uma ares)a em Gse e somen)e se #o formam uma ares)a de G

D4 o "om'lemen)o dos se%uin)es %rafos

G dado 'or1.

" dado 'or$.

B dado 'or+.

Exerccio 0.Defina a u#io dos %rafos G e"'or

A uni2o G " * um %rafoW.

Exerccio .Tm %rafo * ":amado de &om0l")o sobre V se )odo 'ar de v*r)i"es de V * uma ares)a do %rafo ou se(aE

M . Tm %rafo "om'le)o "om n v*r)i"es * deno)ado 'or #. 6rove -ue

Exerccio 5.,onsidere o "aso %eral do e#er""io 1 Tm -umi"o dese(a embar"ar os 'rodu)osp1,p

$,,p

nusando o menor nHmero de "ai#as. Al%uns

'rodu)os n2o 'odem ser "olo"ados num mesmo "ai#as 'or-ue rea%em. Se(a Go %rafo -ue modela esse 'roblema onde v*r)i"es s2o 'rodu)os eares)as os 'ares -ue rea%em e deno)e 'or#QG o nHmero de mnimo de "ai#as de modo -ue se(a 'ossvel en"ai#o)ar os 'rodu)os "om se%urana.6rove -ue

onde m * o nHmero de 'ares de 'rodu)os -ue rea%em.

/$9 @eoria dos Grafos :))'BB'rofessor.ufab".edu.brBC(air.donadelliBdis"i'linasuf'rB"i;0B

/; 11B1$B$;1+ 1;09


4/40

X

1.1. Grau.

6ara um v*r)i"e v -ual-uer num %rafo G definimos os "on(un)os

Q1

e

Q$

esse Hl)imo ":amado de vi/i#a#$a de v. Os elemen)os de$GQv s2o ":amados de vi/i#os de v.

6ara )odo v V QG o nHmero de vi&in:os de v * ":amado de 'rau do v*r)i"e v no %rafo G. Os %raus dos v*r)i"es de um %rafo * um dos seus'arYme)ros im'or)an)es e 'or isso re"ebem uma no)a2o es'e"ial. 6ara um %rafo G M QV,E n2ova&io

%&serva'(o 1.As ve&es su'rimimos os ndi"es ZGou os ar%umen)os ZQG 'ara sim'lifi"ar es"revendo 'or e#em'lo usamos sim'lesmen)eEQv e

$Qv omi)indo os ndi"es da no)a2o ou es"revemos [ 'ara o %rau m#imo e dQv 'ara o %rau de v.

Exemplo $.No e#em'lo 1en"on)ramos dQ5 M KEQ5K M dQ M KEQK M 1 e dQ0 M KEQ0K M $. @amb*m o %rau m#imo * [QG M $ o %rau mnimo *)QG M ; e o %rau m*dio * dQG M 0*/.

T"or"ma 1.+ara todo grafo G vale ue

Q5

emonstra'(o.Se(a QV,E em %rafo e defina o "on(un)oX M Qu,e V \E u eP e vamos "on)ar seu nHmero de elemen)os de duas maneirasdis)in)as.

6rimeiro "ada v*r)i"e u'ar)i"i'a de dQu elemen)os deX 'or)an)o

Q7

De'ois "ada ares)a e es) 'resen)e em dois elemen)os deX lo%o

Q9

De Q7 e Q9 )emos Q5.

Corolrio 2.Em todo grafo o n-mero de vrtices com grau mpar par.

emonstra'(o.Se(a G um %rafo. Deno)e 'or/ o sub"on(un)o formado 'elos v*r)i"es em V QG de %rau m'ar e deno)e 'or+ o sub"on(un)o

dos v*r)i"es de %rau 'ar. Tsando -ue/ + M -ue/ + M V QG e o @eorema 1 )emos

Q1;

'or)an)o devemos )er ]u/

dQu 'ar o -ue semen)e * 'ossvel -uando K/K* 'ar.

E-"r&&ios

Exerccio 7.,:i"o e sua es'osa foram a uma fes)a "om )r4s ou)ros "asais. No en"on)ro deles :ouveram vrios a'er)os de m2o. Nin%u*m a'er)ou a

'rF'ria m2o ou a m2o daQo es'osaQo e nin%u*m a'er)ou a m2o da mesma 'essoa mais -ue uma ve&.

A'Fs os "um'rimen)os ,:i"o 'er%un)ou 'ara )odos in"lusive 'ara a es'osa -uan)as m2os "ada um a'er)ou e re"ebeu de "ada 'essoa umares'os)a diferen)e. Qi Uuan)as m2os ,:i"o a'er)ouW Qii Uuan)as m2os a es'osa de ,:i"o a'er)ouW


/; 11B1$B$;1+ 1;09


5/40

Exerccio 9.6rove -ue )QG dQG [QG 'ara )odo %rafo G.

Exerccio 1;.De"ida se 'ode e#is)ir um %rafo G "om v*r)i"es -ue )4m %raus $,+,+,/,/,0. E %raus $,+,/,/,0W

Exerccio 11.Se(a G um %rafo "om 1/ v*r)i"es e $0 ares)as. Se )odo v*r)i"e de G )em %rau + ou 0 -uan)os v*r)i"es de %rau + o %rafo G'ossuiW

Exerccio 1$.6rove -ue em )odo %rafo de ordem 'elo menos $ e#is)em 'elo menos dois v*r)i"es "om o mesmo %rau.

Exerccio 1+.6ara um nHmero na)ural r um %rafo * rr"'ular se )odos os v*r)i"es )4m %rau r. 6ara um %raforre%ular "om n v*r)i"es e m ares)as e#'resse m em fun2o de n e r.

Exerccio 1/.D4 e#em'lo de um %rafo +re%ular -ue n2o * "om'le)o.

Exerccio 10.6rove -ue se KV QGK^ + e )QG en)2o e#is)em v*r)i"es u e v em G dis)in)os e )ais -ue$Qu $Qv0.

Exerccio 1.Dado G o 'rao li#a de G deno)ado 'or LG * o %rafo "u(os v*r)i"es s2o as ares)as de G e um 'ar de v*r)i"es define uma ares)aem LG se e somen)e se esses v*r)i"es s2o ares)as ad(a"en)es em G. Dado Gde)ermine KV QLGK e KEQLGK.

2. Sub'raos

Di&emos -ue o %rafo" * um sub'rao do %rafo G se e somen)e se V Q" V QG eEQ" EQG e nesse "aso es"revemos" G'ara indi"ar-ue" * sub%rafo de G.

Exemplo +.,onsiderando o %rafo G do e#em'lo 1)emos -ue

s2o sub%rafos de G en-uan)o -ue

n(o s2o sub%rafos de G'ois" n2o * %rafo em/ n2o vale V Q/ V QG e em1 n2o valeEQ1 EQG.

Tm sub%rafo" G onde V Q" M V QG * ":amado de sub'rao '"ra!or.

$.1. Sub'rao i#!u/i!o 0or um sub&o#,u#)o !" v(r)i&"s.

Se 2 V QG en)2o es"revemos G_2 'ara o sub'rao i#!u/i!o 0or 3 -ue * o sub%rafo

$.$. Sub'rao i#!u/i!o 0or um sub&o#,u#)o !" ar"s)as.

Se3 M e1,e$,,emPEQG en)2o o sub'rao i#!u/i!o 0or deno)ado )em "omo "on(un)o de v*r)i"es e1e$ eme "omo "on(un)o

de ares)as o 'rF'rio3

Exemplo /.Dos %rafos G" e/ "u(os dia%ramas s2o dados na fi%ura $ 'odemos di&er -ue" * um sub%rafo indu&ido de G en-uan)o -ue/ * umsub%rafo mas n2o * indu&ido.


/; 11B1$B$;1+ 1;09


6/40

Fi'ura 2* Dia%rama dos %rafos G" e/.

$.+. E-"r&&ios.

Exerccio 15.Uuan)os sub%rafos "om'le)os )em o %rafo "om'le)o de ordem nW

Exerccio 17.Des"ubra um sub%rafo indu&ido de

1re%ular e o maior nHmero 'ossvel de ares)as. QUual a rela2o "om a resolu2o do e#er""io $W

5. Cli6u"7 &o#,u#)o i#!"0"#!"#)"7 'rao bi0ar)i!o " &or)"

Se o sub"on(un)o 2 V QG indu& um %rafo "om'le)o em G en)2o ":amamos 2 de &li6u" em G. 3ais es'e"ifi"amen)e se G_2 * um %rafo"om'le)o "om 4 v*r)i"es en)2o di&emos -ue 2 * um 48&li6u" em G.

O "aso 'ar)i"ular de um +"li-ue num %rafo G * ":amado de tri5ngulo de G.

6or ou)ro lado )odo sub"on(un)o de v*r)i"es 2 V QG )al -ue G_2 M Q2, * ":amado de &o#,u#)o i#!"0"#!"#)"de G ou 48&o#,u#)o8i#!"0"#!"#)" no "aso K2K M 4.

Exemplo 0.O sub%rafo G do e#em'lo +* um +"li-ue e G do e#em'lo +* um +"on(un)oinde'enden)e.

No %rafo G do e#em'lo 1os "on(un)os +,0,P e 1,/,,7P s2o inde'enden)es no "aso de 1,/,,7P )emos um "on(un)o inde'enden)e de"ardinalidade m#ima 'ois n2o : na-uele %rafo "on(un)o inde'enden)e "om 0 ou mais v*r)i"es. Nesse mesmo %rafo 7P ,5P e 1,$,0P s2o"li-ues o Hl)imo de "ardinalidade m#ima.

%&serva'(o $ Qleia esse avisoan)es.O )aman:o do maior "li-uee o )aman:o do maior "on(un)o inde'enden)enum %rafo G s2o dif"eis de serem"al"ulados "om'u)a"ionalmen)e. Eles 'er)en"em a "lasse dos 'roblemasN6dif"eis. Tma "onse-4n"ia desse fa)o * -ue n2o * sabido se e#is)emal%ori)mos "u(o )em'o de e#e"u2o no 'ior "aso * um 'olincmio em KV QGK KEQGK 'ara resolver esse 'roblemas. A des"ober)a de um al%ori)mo"om )em'o de 'ior "aso 'olinomial no )aman:o de G ou a 'rova de -ue ele n2o e#is)e * um dos 'roblemas n2oresolvidos mais im'or)an)es da

a)ualidade o 'roblema 6 \ N6. @ra)ase de um dos 5'roblemas do mil4nio dos -uais res)am n2o resolvidos "ada um "om uma re"om'ensa deTS1.;;;.;;;;; 'ara uma solu2o.

,:amamos um %rafo G de 'rao bi0ar)i!o se e#is)em dois "on(un)os inde'enden)esA eB em G -ueparticionam V QG is)o * )ais -ueA BM eA B M V QG. 6or e#em'lo o se%uin)e %rafo * bi'ar)ido

'ois V QG M 1,$,+,/,0P,5,7P e )an)o 1,$,+,/,0P -uan)o ,5,7P s2o "on(un)os inde'enden)es.

Tm %rafo bi'ar)ido G "ompartes A eB * di)o &om0l")o se )em KAKKBK ares)as ou se(aEQG M a, &PV QG a Ae & BP. Tm %rafo

bi'ar)ido "om'le)o "om 'ar)es de "ardinalidade n e m * deno)ado 'or #,m.

Se(am G um %rafoA eB V QG dois sub"on(un)os dis(un)os em V QG. Definimos o sub"on(un)o de ares)as

Q11

e o sub'rao bi0ar)i!o i#!u/i!o'orA eB * o %rafo bi'ar)ido

O "on(un)o de ares)asEQA,A * ":amado de &or)" !"i#i!o 0orA e Q11 'or dessa forma 'odemos es"rever

Q1$

%&serva'(o +.,onven"ionamos -ue os %rafos )riviais e va&io s2o %rafos bi'ar)idos.

+.1. E-"r&&ios.


/; 11B1$B$;1+ 1;09


7/40

Exerccio 19.3os)re -ue em ualuer %rafo G "om 'elo menos v*r)i"es ou e#is)e um +"li-ue ou e#is)e um +"on(un)oinde'enden)e. QDi"ae#er""io e'rin"'io da "asa dos 'ombossobreE

6Qv.

Exerccio $;.Dado um %rafo G deno)amos 'or 7QG a "ardinalidade do maior "on(un)o inde'enden)e em G

6rove -ue se dQG 8 7QG en)2o G "on)*m )riYn%ulo 'ara )odo G.

Exerccio $1.6ara )odo %rafo G deno)amos 'or 9QG a "ardinalidade do maior "li-ue em G

6rove -ue 9QG M 7QG.

Exerccio $$.Redefina 'ara )odo %rafo G o 'arYme)ro#QG dado no e#er""io 5em fun2o dos "on(un)osinde'enden)es de G. Esse 'arYme)ro de um %rafo * "on:e"ido na li)era)ura "omo nHmero "rom)i"odo %rafo.

Exerccio $+.6rove -ue as duas desi%ualdades dadas a se%uir valem 'ara )odo %rafo G "om 'elo menos um v*r)i"e

Q1+

Exerccio $/.6rove -ueEQA,B MEQB,A se%undo a defini2o dada em Q11.

Exerccio $0.Se(a G M QA B,E um %rafo bi'ar)ido -ual-uer e su'on:a -ue KAK : KBK. verdade -ue 7QG M KBKW De)ermine 9QG.

Exerccio $.6rove -ue G * bi'ar)ido se e somen)e se#QG : +.

Exerccio $5.6rove a afirma2o da e-ua2o Q1$.

Exerccio $7.Dado um %rafo G defina 'ara )odo 2 V QG a vi/i#a#$a !" 2 deno)ada$GQ2 'or

verdade -ue KEQ2,2K M K$GQ2KW Jus)ifi-ue.

Exerccio $9.Tm %rafo G * di)o 480ar)i!o 'ara 4 se e#is)em 4 "on(un)os inde'enden)esA1A

$ A

4-ue

'ar)i"ionam V QG ou se(a V QG MA1A

$ A

4 o "on(un)oA

i* um "on(un)o inde'enden)e em G'ara )odo i

1,$,,4P eAiA

;M 'ara -uais-uer i e; dis)in)os. 6rove -ue den)re os %rafos 4'ar)idos Q4 ^ + "om'le)os "om n v*r)i"es o nHmero m#imo

de ares)as * a)in%ido -uando KAiKgKA

;K 1 'ara )odos i, ; 1, $,, nP dis)in)os.

Exerccio +;.3os)re -ue se n M 4 r "om ; r : 4 en)2o o nHmero de ares)as do %rafo do e#er""io an)erior *

e -ue esse nHmero * limi)ado 'or

4. Isomorismo

Di&emos -ue os %rafos G e" s2o isomoros e nesse "aso es"revemos G " se e#is)e uma fun2o bi(e)ora

Q1/

)al -ue


/; 11B1$B$;1+ 1;09


8/40

Q10

'ara )odos u, v V QG. Tma fun2of "omo a"ima * ":amada de isomorismo.

Exemplo QGrafo de 6e)ersen.Os %rafos re'resen)ados na fi%ura +s2o isomorfos 'elo isomorfismofQ1 M afQ$ M &fQ+ M cfQ/ M dfQ0 M efQ MffQ5 MgfQ7 M


9/40

Nesse e#em'lo foram dados ar%umen)os diferen)es 'ara "on"luir o mesmo fa)o o n(o=isomorfismo en)re 'ares de %rafos. Ainda e#is)eme#em'los de %rafos n2o isomorfos 'ara os -uais esses ar%umen)os n2o fun"ionam Qda mesma forma -ue a e#is)4n"ia de um v*r)i"e de %rau -ua)rofun"iona 'ara mos)rar -ue G n2o * isomorfo a" mas n2o serve 'ara mos)rar -ue G n2o * isomorfo a6'ois 1,$,$,+,+,+ s2o os %raus dos v*r)i"esde ambos os %rafos. Isso se deve ao fa)o de ser dif"il "ara")eri&ar de modo efi"ien)e o n2oisomorfismo en)re %rafos

% pro&lema do n(o=isomorfismo de grafos Dados os %rafos G M QV,E e" M QV,E de"idir se eles s2o n2oisomorfos.

%&serva'(o / Qleia esse avisoan)es.N2o se "on:e"e al%ori)mo de )em'o 'olinomial no )aman:o dos %rafos 'ara de"idir se dois %rafos n2o s2oisomorfos. 3ais do -ue isso n2o se "on:e"e um al%ori)mo de )em'o 'olinomial -ue re"eba "omo en)rada uma )erna QG,",+ onde+ * uma 'rova

de -ue G e" n2o s2o isomorfos e -ue devolvasim se G1n2o * isomorfo a G$e devolva n(o "aso "on)rrio. Em lin%ua%em )*"ni"a dissemos -uen(o se sa&e seo pro&lema do n(o=isomorfismo de grafos est> na classeN6de complexidade computacional.

6or ou)ro lado 'odemos "onsiderar o 'roblema do isomorfismo de %rafos

% pro&lema do isomorfismo de grafos Dados os %rafos G M QV,E e" M QV,E de"idir se eles s2o isomorfos.

%&serva'(o 0 Qleia esse avisoan)es.A)ualmen)e n2o se "on:e"e al%ori)mo 'olinomial no )aman:o do %rafo -ue resolva o 'roblema. En)re)an)on2o * dif"il 'ro(e)ar um al%ori)mo de )em'o 'olinomial -ue re"ebe a )erna QG, ", f ondef V QG V Q" e devolvesim "aso G e" s2oisomorfos ef * o isomorfismo "aso "on)rrio devolve n(o. Em lin%ua%em )*"ni"a di&emos -ue o pro&lema do isomorfismo de grafos est> naclasseN6 decomplexidade de pro&lemas computacionais. En)re)an)o n2o * sabido se esse 'roblema *N6"om'le)o

/.1. E-"r&&ios.

Exerccio +1.De)ermine -uais 'ares den)re os %rafos abai#o s2o isomorfos.

G1dado 'or V QG

1 M v

1,u

1,?

1,x

1,@

1,

1P e

EQG1 M u1,v1P,u1,?1P,v1,?1P,v1,x1P,?1,@1P,x1,@1P,x1,1PP

1.

G$dado 'or V QG$ M v$,u$,?$,x$,@$,$P e

EQG$ M u$,v$P,u$,?$P,v$,?$P,v$,x$P,?$,@$P,x$,@$P,@$,$PP

$.

G+dado 'or V QG+ M v+,u+,?+,x+,@+,+P e

EQG+ M u

+,v

+P,u

+,?

+P,v

+,?

+P,v

+,x

+P,?

+,@

+P,x

+,@

+P,u

+,

+PP.

+.

Exerccio +$.3os)re -ue e#is)em 11 %rafos n2oisomorfos "om / v*r)i"es.

Exerccio ++.Se(am G e" %rafos isomorfos ef V QG V Q" um isomorfismo. verdade -ue G_2 * isomorfo a"_fQ2` 'ara )odo 2 VQGW Jus)ifi-ue.

Exerccio +/.Tm au)omorismo de um %rafo * um isomorfismo do %rafo sobre ele mesmo. Uuan)os au)omorfismos)em um %rafo "om'le)oW

Exerccio +0.3os)re -ue o "on(un)o de au)omorfismos de um %rafo "om a o'era2o de "om'osi2o de fun!es definem um %ru'o.

Exerccio +.Tm %rafo G M QV,E * v(r)i&"8)ra#si)ivo se 'ara -uais-uer u,v V e#is)e um au)omorfismofde G "omfQv M u. Analo%amen)e G *ar"s)a8)ra#si)ivo se 'ara -uais-uer ares)as x,@P,,?PE e#is)e um au)omorfismof de G )al -ue fQx,fQ@P M ,?P.

D4 um e#em'lo de %rafo v*r)i"e)ransi)ivo. D4 um e#em'lo de %rafo ares)a)ransi)ivo. D4 um e#em'lo de %rafo ares)a)ransi)ivo mas n2ov*r)i"e)ransi)ivo.

:. Ou)ras #o$%"s !" 'raos

Em al%umas si)ua!es 'odemos )er um modelo 'ara um 'roblema a ser resolvido e esse modelo seria um %rafo se des"onsiderassemos al%umas'e"uliaridades da si)ua2o. 6or e#em'lo um ma'a rodovirio 'ode ser modelado definindose um v*r)i"e 'ara "ada "idade e duas "idadesformam uma ares)a no %rafo Qmodelo se e#is)e rodovia li%ando essas "idades "orres'onden)es aos v*r)i"es. Normalmen)e dis)Yn"ia * um

'arYme)ro im'or)an)e nesses ma'as e assim as ares)as devem )er um "om'rimen)o asso"iado a elas. En)re)an)o j"om'rimen)o de ares)ak n2o fa&'ar)e da defini2o de um %rafo. Num ou)ro e#em'lo se es)amos in)eressados em ro)as de )rfe%o den)ro de uma "idade 'odemos definir umv*r)i"e 'or es-uina e duas es-uinas "onse"u)ivas numa mesma rua formam uma ares)a. Nesse "aso as ruas )4m sen)ido Qm2o e "on)ram2o e asares)as )amb*m deveriam )er mas novamen)e essa "ara")ers)i"a n2o fa& 'ar)e da defini2o de %rafos.

Esses 'roblemas e mui)os ou)ros 'odem ser modelados "om jou)ros )i'osk de %rafos. Al%uns desses ou)ros )i'os s2o

Grao &om 0"sos #as ar"s)as * um )ri'la QV,E, de modo -ue QV,E * um %rafo eE * uma fun2o -ue assume valores em . O


/; 11B1$B$;1+ 1;09


10/40

"on(un)o em %eral de'ende do 'roblema sendo "onsiderado. 6or e#em'lo se os 'esos re'resen)am dis)Yn"ia en)2o )omamos M Qreaisn2one%a)ivos. O %rafo QV,E * ":amado 'rao sub,a&"#)" do %rafo "om 'esos nas ares)as.

Grao ori"#)a!o * a-uele onde as ares)as )4m uma orien)a2o Qs2o 'ares ordenados de modo -ue se u e v s2o v*r)i"es en)2o Qu,v0Qv,u eal*m disso se Qu,v * uma ares)a en)2o Qv,u n2o * ares)a. Removendo o sen)ido das ares)as )emos o 'rao sub,a&"#)" ao %rafo orien)ado.

Graos !iri'i!o ou !i'rao * dado QV,E ondeE V \ V Qv,v v V P.

ul)i'rao * dado 'or um "on(un)ode v*r)i"es e 'odemos )er mais de uma ares)a in"iden)e ao mesmo 'ar de v*r)i"es. Removendo as ares)asre'e)idas de um mul)i%rafo )emos o 'rao sub,a&"#)" ao mul)i%rafo.

Fi'ura


11/40

Fi'ura ?* Lis)a de ad(a"4n"ias do %rafo G no e#em'lo 7.

%&serva'(o .A re'resen)a2o de uma %rafo 'or lis)a de ad(a"4n"ias n2o * Hni"a 'ois -ual-uer 'ermu)a2o dos nFs em$_i` define uma lis)avlida.

.+. Com0l"-i!a!" !" al'ori)mos "m 'raos.

Nes)e )e#)o en)endemos 'or "om'le#idade do al%ori)mo a

complexidade de tempo no pior caso.

Exemplo 11.Se(amA eB dois al%ori)mos dis)in)os -ue e#e"u)am a mesma )arefa sobre um %rafo G M QV,E. O al%ori)moA %as)a no 'ior "aso KV K$

'assos 'ara e#e"u)ar a )arefa e o al%ori)moB %as)a QKV K KEKlo% KEK 'assos no 'ior "aso. 6ara %rafos "om KV K$*/ ares)as o 'rimeiro al%ori)mo *sem're mel:or en-uan)o -ue 'ara %rafos "om 1.;;;KV K ares)as o se%undo al%ori)mo * assin)o)i"amen)e mel:or Qmel:or 'ara KV K^ 1./0en-uan)o -ue o 'rimeiro * mel:or 'ara KV K 1.//. 6ara en)radas 'e-uenas Qa)* $0 mil v*r)i"es a ordem das fun!es s2o "om'aradas nos%rfi"os da fi%ura 9.

Fi'ura 9* Grfi"o das fun!es do e#em'lo 11.

Tsualmen)e a e#'ress2o -ue es)abele"e a "om'le#idade de um al%ori)mo * es"ri)a em fun2o do )aman:o da re'resen)a2o usada e emno)a2o assin)F)i"a se(amf,g duas fun!es definidas nos na)urais en)2o

si%nifi"a -ue e#is)em "ons)an)es 'osi)ivas c e n;)ais -ue 0ara )o!o# ^ #

@vale

No nosso "aso n * o taman


12/40

'or)an)o 'ara jDevolvaEk * mais efi"ien)e usar lis)as -uando )emos 'ou"as ares)as. As ve&es a "om'ara2o en)re o desem'en:o 'ode ser mais"om'li"ada.

%&serva'(o 5.Tm al%ori)mo em %rafo * de "om'le#idade 'olinomial se a "om'le#idade de )em'o no 'ior "aso * e#'ressa 'or uma fun2o'olinomial no )aman:o da re'resen)a2o. ,om'le#idade 'olinomial * inde'enden)e da re'resen)a2o do %rafo 'or ma)ri& ou lis)a de ad(a"4n"iasou se(a essas re'resen)a!es s2opolinomialmenterelacionadas.

E-"r&&ios

Exerccio /;.3os)re -ue sefQn M %QgQn en)2o %QfQn %QgQn M %QgQn.

Exerccio /1. verdade -ue 'ara )odo G vale -ue KEQGK M %QKV QGK 'ara KV QGK sufi"ien)emen)e %randeW

Exerccio /$. verdade -ue 'ara )odo G vale -ue lo% KEQGK M %Qlo% KV QGK 'ara KV QGK sufi"ien)emen)e %randeW

Exerccio /+.6rove o afirma2o fei)a na observa2o 5.

Exerccio //.Se(am G um %rafoA a sua ma)ri& de ad(a"4n"ias e &Qi,; as en)radas da ma)ri&A$. Uue 'arYme)ro de G es) asso"iado ao nHmero

&Qi,i 'ara "ada i 1,$,,KV QGKPW Uual a rela2o en)re &Qi,; e$GQi e$

GQ; -uando i0;W

Exerccio /0.6ara um %rafo diri%ido di&emos -ue a ares)a Qu,v E sai de u e c


13/40

au)ovalores da ma)ri& de ad(a"4n"ias do %rafo "om'le)o6n. 3os)re -ue se G * rre%ular en)2o r * uma au)ovalor deA.

Exerccio 01.Dada uma re'resen)a2o 'or lis)as de ad(a"4n"ias de um %rafo diri%ido des"reva um al%ori)mo "om )em'o de e#e"u2o %QKV QK KEQK 'ara "om'u)ar a re'resen)a2o 'or lis)as de ad(a"4n"ias do %rafo sub(a"en)e.

Exerccio 0$.Uuando uma re'resen)a2o 'or uma ma)ri& de ad(a"4n"ias * u)ili&ada mui)os al%ori)mos sobre %rafos %as)am )em'o QKV K$ mase#is)em al%umas e#"e!es. 3os)re -ue de)erminar se um %rafo orien)ado "on)*m umsorvedouro is)o * um v*r)i"e "om %rau de en)rada KV Kg 1e %rau de sada ; 'ode ser de)erminado em )em'o %QKV K -uando uma re'resen)a2o 'or ma)ri& * u)ili&ada.


14/40

X

X

X

X

X

lin:a 1 ou 9 o v*r)i"e ? * mar"ado visitado lo%o a "ondi2o 'ara inser2o de ? emF'assa a ser falsa. A 'ro'osi2o se%ue do fa)o de -ue um v*r)i"e visitado nun"a se )ornarn(o=visitado duran)e uma e#e"u2o doal%ori)mos.

ro0osi$o ;.A linximo dGQ? 1 vees, para cada ? V QG.

emonstra'(o.>i#e um v*r)i"e ? e assuma -ue ? F. 6ara "ada e#e"u2o da lin:a + "om u M ? se vale a "ondi2o da lin:a /en)2o o nHmero de ares)as n(o=visitadas a partirde ? emEQ? diminui de um sen2o ? * removido deF. ,omo "onse-4n"ia ser2o; ares)as n(o=visitadas a partir de ? a'Fs dQ? e#e"u!es mais 1 e#e"u2o -ue resul)a naremo2o de ? da lis)aF. O resul)adose%ue da 'ro'osi2o an)erior.

Corolrio "ma ?.$uma execu'(o de isi)eQGv todo vrtice alcan'>vel a partir de v visitado.

emonstra'(o.Se(a ? V QG um v*r)i"e al"anvel a 'ar)ir de v. 6or defini2o e#is)e uma se-4n"ia

Q1

de ares)as de G )al -ue

amos 'rovar 'or indu2o em m -ue se ? * al"anvel a 'ar)ir de v'or uma se-4n"ia de m ares)as en)2o ? * visi)ado.

6ara a base da indu2o su'on:a m M 1 e es"reva e1M v,?P. Na lin:a 1 do al%ori)mo isi)eQGv o v*r)i"e v * visi)ado e en)ra emF. 6elo"orolrio5v * removido em al%um

momen)o da e#e"u2o e an)es disso a ares)a e1vai ser visi)ada a 'ar)ir de v na lin:a 9 nesse 'on)o ou ?(foi visi)ado ou vale a "ondi2o da lin:a 7 e ? * visi)ado.

Su'on:a Q:i'F)ese da indu2o -ue )odo v*r)i"e al"anvel a 'ar)ir de v'or uma se-4n"ia de mg 1 ares)as * visi)ado. Se(a ? um v*r)i"e"omo emQ1.

Es"reva em

M x,?P "omx em e

mg1. 6or :i'F)esex foi visi)ado 'or)an)o an)es de ser removido a ares)a x,?PEQx * visi)ada a'ar)ir dex e assim ? * visi)ado 'elo mesmo

ar%umen)o dado na :i'F)ese de indu2o.

Corolrio 9.De;a A o su&con;unto dos vrtices de V QG alcan'>veis a partir de v. Ent(o cada aresta de G_A` visitada duas vees.

emonstra'(o.Se(a e M x,@P uma ares)a de G_A`. ,omox,@ A )emosx F em al%um momen)o da e#e"u2o de isi)eQGvan)es dex ser removido deF a ares)a e * visi)ada a'ar)ir dex. Analo%amen)e a ares)a e * visi)ada a 'ar)ir de@ lo%o a ares)a *visi)ada duas ve&es.

Desse "orolrio 'odemos "on"luir -ue a "om'le#idade de isi)eQG,v * Qlinearmen)e 'ro'or"ional ao )aman:o da re'resen)a2o is)o *%QKAK KEQG_A`K Qlembrese -ue foiassumido "us)o "ons)an)e 'ara as o'era!es emF.

A%ora * sim'les mos)rar -ue o se%uin)e al%ori)mo 'er"orre o %rafo QV,E visi)ando "ada v*r)i"e uma Hni"a ve& e visi)ando "ada ares)a duasve&es e "om "om'le#idade de )em'o %QKV K KEK.

Visite

h vrtice no-visitado em

escolha no-visitado;

insira em e marque ;

escolha ;

em h aresta no-visitada a partir de

escolha no-visitada a partir de ;

marque a partir de ;

no-visitado


remova de .

5.$. E-"r&&ios.

Exerccio 0+.Jus)ifi-ue de)al:adamen)e o "us)o %Q1 nas lin:as do al%ori)mo isi)eQGv.

Exerccio 0/.6rove -ue se G es) re'resen)ado 'or uma ma)ri& de ad(a"4n"ias en)2o o al%ori)mo isi)e )em "om'le#idade %QKV QGK$.


de /; 11B1$B$;1+ 1;09


15/40

Exerccio 00.Es"reva um al%ori)mo -ue re"ebe um %rafo G e um sub"on(un)o de v*r)i"es 2 e devolve as ares)as no "or)eEQ2,2. De)ermine a"om'le#idade do al%ori)mo.

Exerccio 0.Se(a G um %rafo. 6ara sim'lifi"ar su'on:a -ue )odo v*r)i"e de G * al"anvel a 'ar)ir de -ual-uer v*r)i"e dado. 6ara "ada v*r)i"e)emos dois es)ados 'ossveis n(o=visitado ou visitado. De in"io )odos os v*r)i"es de G es)2o n(o=visitado. 6rove ou refu)e o se%uin)e al%ori)movisi)a )odos os v*r)i"es de G.

Visite-vertices

escolha um vrtice no-visitado;


houver aresta no corte

escolha uma aresta no corte ;

no-visitado

ento insira em ;

marque visitado.

Exerccio 05.De)ermine a "om'le#idade do al%ori)mo do e#er""io an)erior.

?. Al'ori)mos !" bus&a

Algoritmo de &usca * "omo s2o ":amados usualmen)e al%uns dos al%ori)mos de 'er"urso em %rafos.

%&serva'(o 7 Qleia esse avisoan)es.Se vo"4 es) in)eressado em al%ori)mo de bus"a en)2o 'ode "omear 'elos al%ori)mos de bus"ades"ri)os na?i4ipedia.

Nessa se2o veremos dois "asos 'ar)i"ulares do al%ori)mo de 'er"urso vis)o a"ima ob)idos -uando definimos a 'ol)i"a de %eren"iamen)o dalis)aF. A es)ra)*%ia %eral de bus"a * a 'ar)ir do v*r)i"e v dado se :ouver v*r)i"e un2ovisi)ado en)2o visi)e u e seus vi&in:os n2ovisi)ados. 6aravisi)ar os vi&in:os de u'odemos des)a"ar duas es)ra)*%ias

7.1. Bus&a "m >ar'ura.

'rimeiro visi)amos "ada vi&in:o novo de v 'er"orrendo$Qv e %uardamoso numa fila -uando n2o :ouver mais vi&in:os mar"amos v "omovisi)ado 'e%amos o 'rimeiro v*r)i"e da fila e re'e)imos o 'ro"esso. Em ou)ras 'alavras a lis)aF * adminis)rada "omo ila.

Visite_em_Largura

1 insira no fim da fila e marque ;

2

3 seja o primeiro vrtice da fila;

4 em h aresta no-visitada a partir de

6 escolha no-visitada a partir de ;

7 marque a partir de ;

8 no-visitado

9 insira no fim da fila e marque ;

10 remova da fila .

Exemplo 1$.Na fi%ura 1;mos)ramos um es-uema de 'er"urso em lar%ura su'ondo -ue os v*r)i"es es)2o arma&enados em ordem "res"en)e na lis)a

de ad(a"4n"ias. As ares)as des)a"adas indi"am -uando um v*r)i"e "om a mar"a n(o=visitado foi visi)ado.

Fi'ura 1@* E#em'lo de bus"a em lar%ura.

7.$. Bus&a "m rou#!i!a!".

visi)amos "ada vi&in:o novo de v 'er"orrendo$Qv e %uardamoso numa 'il:a -uando n2o :ouver mais vi&in:os mar"amos v "omo visi)ado'e%amos o 'rimeiro v*r)i"e da 'il:a e re'e)imos o 'ro"esso.Em ou)ras 'alavras a lis)aFa"ima * adminis)rada "omo 0ila.

Exemplo 1+.Na fi%ura 11mos)ramos o es-uema de um 'er"urso em 'rofundidade. As ares)as des)a"adas indi"am -uando um v*r)i"e "om a mar"an(o=visitado foi visi)ado.


de /; 11B1$B$;1+ 1;09


16/40

Fi'ura 11* E#em'lo de bus"a em 'rofundidade.

Exemplo 1/.6or fim a fi%ura 1$"om'ara as ordens em -ue os v*r)i"es foram des"ober)os em "ada uma das bus"as lar%ura e 'rofundidaderes'e")ivamen)e.

Fi'ura 12* ,om'ara2o das bus"as em lar%ura e em 'rofundidade.

%&serva'(o 9 Qleia esse avisoan)es.e(a as en)radas no Ki4ipedia'arabus"a em lar%urae 'arabus"a em 'rofundidade.

7.$.1.Busca em profundidade rotulada.A se%uin)e vers2o da bus"a em 'rofundidade ser mui)o H)il adian)e ":amaremosa de &usca emprofundidade rotulada e a id*ia * man)er um "on)ador Q%lobal de o'era!es na 'il:a e ro)ular "ada v*r)i"es "om dois valores in)eiros o valor do"on)ador -uando o v*r)i"e en)rou na 'il:a e o o valor do "on)ador -uando o v*r)i"e saiu da 'il:a. A se%uir damos uma vers2o re"ursiva 'ara o

'ro"edimen)o isi)e da bus"a ro)ulada o -ual re"ebe um %rafo G dado 'or uma lis)a de ad(a"4n"ias e um v*r)i"e ? V QG no in"io )emos cont

Msai_v` M c


17/40

7.+. E-"r&&ios.

Exerccio 07.Es"reva uma vers2o n2o re"ursiva da bus"a em 'rofundidade ro)ulada.

Exerccio 09.6rove a 'ro'osi2o 1;.

Exerccio ;.,onsidere uma e#e"u2o da bus"a ro)ulada 86QG,?. 6ara sim'lifi"ar "onsidere -ue )odo v*r)i"e de G * al"anvel a 'ar)ir de ?.

6rove as se%uin)es e-uival4n"ias. 6ara -uais-uer u,v V QG

c


18/40

X

Exemplo 1.No %rafo do e#em'lo 10)emos dis)GQa,; M dis)

GQa,& M 1 dis)

GQa,i M + dis)

GQm,; M . Observe -ue o "amin:o de "om'rimen)o

mnimo 'ode n2o ser Hni"o.

%&serva'(o 1; Qdesigualdade triangular.6ara )odo G e )odos u,v V QG )emos dis)GQu,v M dis)

GQv,u. @amb*m se%ue da defini2o -ue

dis)GQv,u M ; se e somen)e se u M v e -ue vale a desi%ualdade )rian%ular

Q$1

'ara -uais-uer u,v,? V QG dis)in)os. 6or)an)o a dis)Yn"ia define uma m*)ri"aem G.

Definimos o !im")ro do %rafo G "omo a maior dis)Yn"ia en)re dois v*r)i"es -uais-uer de G ou se(a

Q$$

Na)uralmen)e diamQG M se e#is)irem dois v*r)i"es no %rafo G -ue n2o s2o li%ados 'or "amin:o.

Tm &ir&ui)o * -ual-uer %rafo QV,E da forma

Q$+

'ara al%um 4 ^ $.

,omo no "aso do "amin:o 'ara sim'lifi"ar o "ir"ui)o definido em Q$+ )amb*m * deno)ado 'ela se-4n"ia de seus v*r)i"es

"om os "uidados de )odos os v*r)i"es a menos do 'rimeiro e do Hl)imo serem dis)in)os e de v*r)i"es "onse"u)ivos serem ad(a"en)es. O nHmero deares)as num "ir"ui)o * o &om0rim"#)o desse "ir"ui)o e -uando -ueremos des)a"ar o "om'rimen)o deno)amos um "ir"ui)o de "om'rimen)o 4'orC4.

Exemplo 15.,onsideremos o %rafo G do e#em'lo 10)emos -ue C/M G &,d,e,gP * um "ir"ui)o bem "omo o sub%rafo C0M QV,E definido 'or V M

a,&,d,e,gP eE M a&,&e,eg,gd,daP.

ro0osi$o 11.odo grafo G contm um camin


19/40

u$,, u4, v1,v$,,vM. Su'ondo -ue+ e L se(am "amin:os no %rafo sob -ue "ondi!es a se-4n"ia+,L * "amin:oW

Exerccio /.6rove a desi%ualdade )rian%ular Qe-ua2o Q$1.

Exerccio 0.Es"reva um al%ori)mo -ue re"ebe uma %rafo G e de"ide se G * um "amin:o. Es)abelea a "om'le#idade do al%ori)mo.

Exerccio .Es"reva um al%ori)mo baseado numa bus"a em lar%ura -ue re"ebe QV,E e v*r)i"es v,? V e devolve dis)GQ?,v.

Exerccio 5.6rove -ue G * bi'ar)ido se e somen)e se G n2o "on)*m "ir"ui)o de "om'rimen)os m'ar.

Exerccio 7.Se(a G um %rafo onde a dis)Yn"ia en)re -ual-uer 'ar de v*r)i"es * fini)a. 3os)re -ue se e#is)em ? V QG e uv EQG )ais -uedis)Q?,u M dis)Q?,v en)2o G "on)*m um "ir"ui)o de "om'rimen)o m'ar. 3os)re -ue "in QG dis)Q?,u dis)Q?,v 1.

Exerccio 9.3os)re -ue a rela2o e f emEQG dada 'or e Mf ou e#is)e um "ir"ui)o C G )al -ue e ef'er)en"em aEQC * uma rela2o dee-uival4n"ia.

Exerccio 5;.Se(a 4 um nHmero na)ural. O 48&ubo * o %rafo "u(o "on(un)o de v*r)i"es s2o as se-en"ias binrias de 4bi)s e dois v*r)i"es s2o ad(a"en)es se e somen)e se as 4)u'las "orres'onden)es diferem e#a)amen)e em uma 'osi2o.

De)ermine o nHmero de v*r)i"es ares)as o diYme)ro e a "in)ura do 4"ubo. De)ermine os 'arYme)ros 7 9 e# do 4"ubo.

Fi'ura 1:* E#em'lo o +"ubo.

Exerccio 51.Se(a 4 um nHmero na)ural. O 'rao !" Fibo#a&&i!4* o %rafo "u(o "on(un)o de v*r)i"es s2o as

se-en"ias binrias de 4bi)s sem bi)s 1 "onse"u)ivos e dois v*r)i"es s2o ad(a"en)es se e somen)e se as 4)u'las"orres'onden)es diferem e#a)amen)e em uma 'osi2o. De)ermine o nHmero de v*r)i"es ares)as o diYme)ro e a "in)ura do!

4. De)ermine os

'arYme)ros 7 9 e# do!4.

Exerccio 5$.Se(ap um nHmero 'rimo e )ome V M ;,1,,pg1P. Defina o %rafo bi'ar)ido +re%ular G M QAB,E "omA M V \ aP eB M V \&P Qo-ue -ueremos * -ueA eB se(am duas "F'ias dis(un)as de V no)e -ue isso n2o * 'ossvel )omandoA M V eB M V . ,ada v*r)i"e Qx,a A *ad(a"en)e aos v*r)i"es Qx,& Qx 1,& e Qx @, & deB onde@0;,1 * fi#o e a soma * fei)a mFdulop.

6rove -ue -ual-uer sub%rafo indu&ido de G de ordemp 1 "on)*m um "amin:o de "om'rimen)o $ -uando@ M $, Qp 1*$,p g 1.

Re'i)a 'ara -ual-uer@0;,1.

1@. Cami#os m#imos "m 'raos &om 0"sos #as ar"s)as

Nes)a se2o "onsideramos %rafos "om 'eso nas ares)as esses %rafos s2o definidos 'or uma )erna QV,E, onde V eE s2o os usuais "on(un)os dev*r)i"es e ares)as res'e")ivamen)e eEQG * uma fun2o -ue a)ribui um 'eso a "ada ares)a deE Qa-ui re'resen)ando o "om'rimen)o daares)a.

O &om0rim"#)o de um "amin:o+ Mx;,x

1,,x

4em QV,E, * a soma dos 'esos Q"om'rimen)os das ares)as no "amin:o

e a !is)#&ia en)re dois v*r)i"es u e v * o "om'rimen)o do menor "amin:o -ue os li%a

-uando e#is)e al%um "amin:o "aso "on)rrio "onven"ionamos -ue dis)Qu,v M )al -ue vale Q$;. Tm "amin:o -ue li%a ua v de "om'rimen)odis)Qu,v : * ":amado de &ami#o m#imo.

Exemplo 17.O dia%rama da fi%ura 1re'resen)a um %rafo "om 'esos nas ares)as.


de /; 11B1$B$;1+ 1;09


20/40

Fi'ura 1;* Dia%rama de um %rafo "om 'eso nas ares)as. A dis)Yn"ia en)re a e e * 1; e um "amin:o mnimo * a, c, &, d, f, e.

No -ue se%ue vamos su'or -ue os %rafos s2o dados 'or lis)a de ad(a"4n"ias onde a lis)a de v "on)*m os v*r)i"es u V QG )ais -ue v,uPEQG (un)o "om o 'esoQu,v.

Exemplo 19.6ara o %rafo G do e#em'lo 17uma lis)a de ad(a"4n"ias * re'resen)ada na fi%ura 15.

Fi'ura 1


21/40

X

X

No in"io d_s` M ; 'oiss es) a dis)Yn"ia ; dele mesmo 'ara -ual-uer v*r)i"e v0s )emos d_v` M D M .

Num de)erminado momen)o da e#e"u2o o "on(un)o D "on)*m os v*r)i"es "u(as dis)Yn"ias ( es)2o de)erminadas. Nesse 'on)o es"ol:emos o

v*r)i"e u D-ue )em menor valor de d_ ` u * o v*r)i"e de DQ"on(un)o dos v*r)i"es "om dis)Yn"ia ainda n2o de)erminada 'elo al%ori)mo mais'rF#imo do v*r)i"e de sadas 'or)an)o sua dis)Yn"ia fi"a de)erminada 'elo valor de d_u` e 'odemos inserilo em D. Em se%uida visi)amos "adavi&in:o t de u Q'or Q$5 distQs, t d_u` Qu,t e )es)amos se um "amin:o de menor "om'rimen)o foi en"on)rado se for o "aso en)2o a)uali&amosd_ `

Relaxao

1

2 .

No)e -ue a "ondi2o na lin:a 1 do al%ori)mo a"ima * sem're falsa 'ara t D. O al%ori)mo 'rosse%ue a)* -ue D M V .

Dijkstra

1 Inicie ;

2

3 vrtice de com minimo;

4 insira em ;

5

6 Relaxao .

Tma demons)ra2o formal de -ue o al%ori)mo fun"iona is)o * no final d_v` arma&ena as dis)Yn"ias dis)Qs,v 'ara )odo v V se%uefa"ilmen)e do )eorema 1/'rovado adian)e. Esse al%ori)mo * "on:e"ido "omo al%ori)mo de Di(


22/40

X

momen)o da e#e"u2o u0s lo%o D0 * 'ossvel)ermosx Ms e@ M u masx0u.

A%ora -uandox en)rou em D o"orreu Rela#a2oQG,x,@ o -ue fe& "om -ue d_@` Mdis)Qs,@ 'ela 'ro'osi2o 1+.

,omo os 'esos n2o s2o ne%a)ivos e+ * mnimodis)Qs,@ dis)Qs,u ou se(a

onde a Hl)ima desi%ualdade vem da 'ro'osi2o 1$Qa. 3as d_u` d_@` 'ois ambos es)2o em De u foi es"ol:idoassim d_u` Mdis)Qs,u e )emos uma "on)radi2o.A "orre2o do al%ori)mo de Di(lise de complexidade.Ini"ieQGs )em "om'le#idade %QKV K e Rela#a2oQu,t "us)a %Q1.

A "om'le#idade do al%ori)mo de Di(


23/40

;

;

diferente de nil

empilhe em ;

;

imprima ;

no-vazia

imprima (desempilhe ).

6rove -ue a res'os)a de Im'rimeZ"amin:oZminimoQGpv * um "amin:o mnimo -ue li%a ? e v.

Exerccio 57.Dado um %rafo "om 'esosEQ _;,1` -ue re'resen)am a 'robabilidade de uma ares)a n2o fal:ar a 'robabilidade de um"amin:o em es)ar o'era"ional * o 'rodu)o das 'robabilidades das ares)as desse "amin:o Qi.e. es)amos su'ondo inde'end4n"ia das

'robabilidades de n2o fal:ar. Es"reva um al%ori)mo 'ara des"obrir o "amin:o mais se%uro en)re dois v*r)i"es. 6rove -ue o al%ori)mo es)"orre)o.

Exerccio 59.Se(a M QV,E, um %rafo "om 'esoE ;,1,,mP nas ares)as m . 3odifi-ue Di(ord devolve o valor booleano 'rome)ido

Q% "on"lua -ue o al%ori)mo de 8ellmanq>ord fun"iona "orre)amen)e.

%&serva'(o 1+ Qleia esse avisoan)es.e(a as en)radas no Ki4ipedia'ara al%ori)mo de 8ellmanq>ord.

Exerccio 71.6rove -ue a "om'le#idade do al%ori)mo de 8ellmanq>ord * %QKV KKEK.

Exerccio 7$ QAl'ori)mo !" Flo!8arsall.Se(a G M QV,E, um %rafo "om 'esos nas ares)as re'resen)ado 'ela ma)ri&


de /; 11B1$B$;1+ 1;09


24/40

A se%uin)e es)ra)*%ia de)ermina dis)GQi,; 'ara )odos i,; V usando uma )*"ni"a 'ara 'ro(e)o de al%ori)mos "on:e"ida "omo'ro%rama2o

dinYmi"a 6ara )odo 4 ;,1,,KV KP deno)amos 'or _4 o sub"on(un)o 1,$,,4PV "om _;` M . Di&emos -ue o "amin:o+ M i,v;,,v

t,; * um

_4"amin:o se o seus v*r)i"es in)ernos v;,,v

t'er)en"em a _4 . ,om isso 'odemos definir uma varian)e da dis)Yn"ia -ue ":amaremos de

_4dis)Yn"ia en)re i e; "omo o "om'rimen)o do menor _4"amin:o -ue li%a i a; e * deno)ada 'or dis)4Qi,; "om dis)

;Qi,; M a

i;.

Fi'ura 1?* O Hni"o _;`"amin:o -ue li%a + e / * +,/ os _1`"amin:os -ue li%am + e / s2o +,/ e +,1,/ os _$`"amin:os -ue li%am + e / s2o+,/ +,1,/ +,$,/ +,1,$,/ e +,$,1,/ esses s2o )amb*m )odos os _+`"amin:os e _/`"amin:os -ue li%am + e /. No %rafo re'resen)adoa"ima d

;Q+,/ M 0 d

1Q+,/ M / e d

$Q+,/ M d

+Q+,/ M d

/Q+,/ M +. @amb*m d

;Q1,$ M d1Q1,$ M d$Q1,$ M 1; d+Q1,$ M / e d/Q1,$ M +.

6or defini2o a _4 1`dis)Yn"ia * o "om'rimen)o do menor _4 1`"amin:o e a _4dis)Yn"ia * o "om'rimen)o do menor _4"amin:o adiferena en)re esses "amin:os * -ue no 'rimeiro os _4 1`"amin:os * 'ossvel -ue o v*r)i"e 4 1 se(a v*r)i"e in)erno e no se%undo n2o 'ois_4 1` M _4 4 1P. Dessa forma

Q$9

Resumindo

Floyd-Warshall

e em V

;

e em V

.

6rove -ue o )em'o de e#e"u2o * %QKV K+ e -ue o al%ori)mo es) "orre)o Qse%ue de Q$9.

%&serva'(o 1/ Qleia esse avisoan)es.e(a a en)rada no Ki4ipedia'ara al%ori)mo de >lodqars:all.

Exerccio 7+.De)ermine diQ;,4 'ara )oda )erna Qi,;,4 V+no %rafo da fi%ura 17.

Exerccio 7/.A se%uin)e vers2o do al%ori)mo de >lodqars:all fun"iona "orre)amen)eW

Floyd-Warshall

e em V

;

e em V

.

Exerccio 70.F"&o )ra#si)ivo Se M QV,E * um %rafo diri%ido en)2o o fe":o )ransi)ivo de * o %rafoM QV, E onde

Es"reva um al%ori)mo de )em'o %QKV K+ 'ara de)erminar o fe":o )ransi)ivo de um %rafo.

12. Co#"-i!a!"

Tm %rafo G * &o#"-o se * n(o=vaio e -uais-uer dois v*r)i"es de G s2o li%ados 'or um "amin:o.

Di&emos -ue" * umsu&grafo conexo maximal de G se n2o e#is)e um sub%rafo "one#o! G )al -ue" !. Os sub%rafos "one#o ma#imais

de um %rafo -ual-uer s2o os &om0o#"#)"s &o#"-os do %rafo. 6or e#em'lo no %rafo do e#em'lo 1)emos -ua)ro "om'onen)es "one#os a saberindu&idas 'elos "on(un)os de v*r)i"es 1,$,0P +,/P ,5P e 7P.

Tm v*r)i"e v V num %rafo "one#o G M QV,E * ":amado de ar)i&ula$o Qou v(r)i&" !" &or)" se a remo2o do v*r)i"e v e das ares)as deEQvem G resul)a num %rafo des"one#o is)o * o %rafo G g vdefinido 'or V gvP,E gEQv * des"one#o.


de /; 11B1$B$;1+ 1;09


25/40

Tm %rafo sem ar)i"ula!es * ":amado de bi&o#"-o. Os sub%rafos bi"one#os ma#imais de um %rafo G -ual-uer s2o ":amados de&om0o#"#)"s bi&o#"-os de G.

Exemplo $;.No %rafo do dia%rama na fi%ura 19s2o ar)i"ula!es os v*r)i"es 1,+,5,9.

Fi'ura 19* 1, +,5,9 s2o ar)i"ula!es.

Os "om'onen)es bi"one#os s2o os sub%rafos indu&idos 'elos "on(un)os de v*r)i"es 1,1+P 1,$,+,/,0,P +, 5P 5, 7P 9,1;P e +,9,11,1$P.

Fi'ura 2@* ,om'onen)es bi"one#os.

1$.1. E-"r&&ios.

Exerccio 7.Dado G M QV,E es"revemos u v 'ara -uais-uer v*r)i"es u e v de G se e somen)e se u M vou e#is)e um "amin:o li%ando u a v em

G. 3os)re -ue * uma rela2o de e-uival4n"ia sobre V e "ara")eri&e as "lasses de e-uival4n"ia dessa rela2o.

Exerccio 75.3os)re -ue se G M QV,E * "one#o en)2o G g "M QV,E eP * "one#o 'ara )oda ares)a e -ue 'er)en"e aal%um "ir"ui)o de G.

Exerccio 77.3os)re -ue se [QG $ en)2o os "om'onen)es "one#os de G ou s2o "amin:os ou s2o "ir"ui)os.

Exerccio 79.Se(a" um sub'rao '"ra!or de G is)o *" G e V Q" M V QG. 3os)re -ue se" * "one#o en)2o G *"one#o.

Exerccio 9;.Se(a G um %rafo "om n v*r)i"es. ,onsidere os %raus dos v*r)i"es em ordem "res"en)e )QG M d1 d

$ dnM [QG. 3os)re -ue se

d4^ 4 vale 'ara )odo 4 "om ; : 4 : n g [QG en)2o G * "one#o.

Exerccio 91.Se(a G o %rafo definido sobre o "on(un)o de v*r)i"es ;,1,,n g 1P "om u,vPEQG se e somen)e se u g v 4mod n.

D4 um "ondi2o ne"essria e sufi"ien)e sobre n e 4'ara -ue G se(a "one#o.1.De)ermine o nHmero de "om'onen)es "one#os em fun2o de n e 4.$.

Exerccio 9$.3os)re -ue se G * "one#o en)2o LG Qve(a e#er""io 1 * "one#o.

Exerccio 9+.3os)re -ue se u n2o * ar)i"ula2o num %rafo "one#o G en)2o )oda ares)a -ue in"ide em u'er)en"e a um "ir"ui)o de G.

Exerccio 9/.6rove ou d4 um "on)rae#em'lo 'ara dado n e#is)e )n)al -ue )odo %rafo "om n e %rau mnimo )

n* bi"one#o.

Exerccio 90.Se u * uma ar)i"ula2o de um %rafo "one#o G en)2o G_$Qu` * "one#oW

Exerccio 9.Dado um sub"on(un)o 2 V QG deno)amos 'or G g 3o sub%rafo indu&ido 'or V QG 2. 6ara )odo 4 di&emos -ue um %rafo G * 48&o#"-o se


de /; 11B1$B$;1+ 1;09


26/40

KV QGK 8 4 e

n2o e#is)e um 2 V QG de "ardinalidade K2K : 4 )al -ue G g 2 * des"one#o.

Assim )odo %rafo n2ova&io * ;"one#o )odo %rafo n2o)rivial e "one#o * 1"one#o e )odo %rafo bi"one#o "om 'elo menos )r4s v*r)i"es *$"one#o. A &o#"-i!a!" de G * o maior in)eiro 4'ara o -ual G * 4"one#o

Q+;

Qi 6rove -ue )odo %rafo 4"one#o )amb*m * M"one#o 'ara )odo M : 4.

Qii 6rove ou refu)e 'ara )odo G vale )QG ^ OQG.

Qiii 6rove -ue 'ara )odo G 4"one#o vale KEQGK^ 4KV QGK*$.

Exerccio 95.Dados 4 ^ $ e n 8 4 vamos "ons)ruir o %rafo"n,4

M QV,E sobre V M ;,1,,n g 1 "om "on(un)o de ares)as -ue de'ende da 'aridade

de 4

Se 4 * 'ar di%amos 4 M $r en)2o

Q+1

1.

Se 4 * m'ar di%amos 4 M $r 1 en)2o

Q$.1 Se n * 'ar

Q+$

Q$.$ Se n * m'ar

Q++

$.

Abai#o )emos res'e")ivamen)e os dia%ramas dos %rafos"7,/

"7,0

e"9,0

.

Qi 6rove -ue o nHmero de ares)as de"n,4

* .

Qii 6rove -ue"n,4

* 4"one#o.

15. rvor"s " Flor"s)as

Tma lor"s)a * um %rafo sem "ir"ui)os. Os "om'onen)es "one#os de uma flores)a s2o rvores ou se(a uma rvor" * um %rafo "one#o sem"ir"ui)os.

Deno)amos 'or G -o %rafo QV QG,EQG x,@PP su'ondo -uex,@ V QG.

T"or"ma 1:.As seguintes afirma'Pes s(o euivalentes para todo grafo G M QV,EQ

G >rvoreR1.

para uaisuer x,@ V existe um -nico camin


27/40

X

X

Esses ndi"es es)2o bem definidos "omo os "amin:os s2o dis)in)os 1 p :minm,nP ep : ; n. A%oraxp, xp1,,x,@Mg1,@Mg$,,@p* um

"ir"ui)o em G uma "on)radi2o. Assim o "amin:o -ue li%ax a@ * Hni"o.

_Q$Q+` Se(a G )al -ue Q$ vale. 6or :i'F)ese G * "one#o. 6ara )oda ares)a e Mx@ E )emos -ue+ Mx,@* o Hni"o "amin:o -ue li%ax a@'or)an)o G g e * des"one#o.

_Q+Q/` Se(a G "one#o minimal. Se G "on)*m "ir"ui)o en)2o 'ara -ual-uer e EQG -ue 'er)ena a um "ir"ui)o )emos -ue G g e * "one#o

Qe#er". 75 uma "on)radi2o. A%ora se(ax,@ V n2o ad(a"en)es em G "omo G * "one#o e#is)e um "amin:o di%amos+ Mx,v1,,v

4,@ li%andox

a@. Em G x@ )emos o "ir"ui)ox, v1,, v4,@,x.

_Q/Q1` Se(a G um %rafo a""li"o ma#imal. ,omo G * a""li"o sF 're"isamos mos)rar -ue * "one#o. Observamos -ue se n2o e#is)e"amin:o li%andox a@ en)2o G x@ n2o "on)*m "ir"ui)o uma "on)radi2o.

Dessa forma fi"a es)abele"ida a e-uival4n"ia das 'ro'osi!es.

,omo "onse-4n"ia do )eorema 10)emos o se%uin)e "orolrio.

Corolrio 1;.2ma >rvore com n vrtices um grafo conexo com o menor n-mero possvel de arestas dentretodos os grafos conexos com nvrtices.

>inalmen)e vamos mos)rar -uan)as ares)as )em um %rafo "one#o minimal sobre n v*r)i"es.

>"ma 1rvore com n vrtices tem n g 1 arestas.

emonstra'(o.amos 'rovar 'or indu2o em n ^ 1 -ue a se%uin)e afirma2o valese um grafo com n vrtices uma >rvore ent(o o n-merode arestas ng1.No %rafo "om 1 v*r)i"e o nHmero de ares)as * ; Qbase da indu2o. amos assumir -ue a afirma2o a"ima vale 'ara n g 1 onden ^ $.

A%ora se(a G uma rvore "om n v*r)i"es. @ome v V QG uma fol:a de G. O %rafo Ggv * uma rvore Q(us)ifi-ue "om n g 1 v*r)i"es e 'ela:i'F)ese indu)iva KEQG g vK M n g $. ,omo KEQvK M 1 )emos -ue KEQGK M n g 1. 6or)an)o 'elo 6rin"'io de Indu2o >ini)a a afirma2o a"ima vale

'ara )odo n ^ 1.

1+.1. rvor"s '"ra!oras.

Se o sub%rafo %erador G * uma rvore en)2o ":amamos de rvor" '"ra!ora de G.

@odo %rafo "one#o )em uma rvore %eradora Se(a G um %rafo "one#o e se(a G um sub%rafo %erador de G "one#o e "om o menor nHmerode ares)as 'ossvel. Se "on)*m "ir"ui)o en)2o 'ara -ual-uer ares)a e de um "ir"ui)o g e * "one#o e )em menos ares)as -ue uma "on)radi2o.

Desse fa)o 'odemos "on"luir -ue a re"'ro"a do lema 15 su'on:a -ue G * "one#o "om n v*r)i"es e ng 1 ares)as. Se(a G uma subrvore%eradora de G. ,omo a"abamos de mos)rar )em ng 1 ares)as lo%o M G. De"orre -ue G * uma rvore.

T"or"ma 1?.2m grafo com n vrtices uma >rvore se, e somente se, conexo e o n-mero de arestas ng 1.

De)erminar uma rvore %eradora de um %rafo "one#o * f"il e r'ido e ( sabemos "omo fa&er * o sub%rafo indu&ido 'elo "on(un)o de ares)as

Q+/

onde o ve)orpai * "omo no al%ori)mo 7.$.1.

Exemplo $1.Tm %rafo "one#o e uma rvore %eradora de)erminada 'or uma bus"a em 'rofundidade.

Fi'ura 21* * a rvore %eradora de G definida 'elo ve)orpai de uma bus"a em 'rofundidade ro)ulada.

1+.$. E-"r&&ios.


de /; 11B1$B$;1+ 1;09


28/40

Exerccio 97.De)ermine o nHmero de ares)as de uma flores)a "om n v*r)i"es e "om 4 "om'onen)es "one#os.

Exerccio 99.Desen:e )odas as rvores n2oisomorfas "om 0 v*r)i"es e )odas as rvores n2oisomorfas "om 5 v*r)i"es e "om %rau m#imo 'elomenos /.

Exerccio 1;;.3os)re -ue )oda rvore )em 'elo menos [Q fol:as.

Exerccio 1;1.6rove -ue o "on(un)o de ares)as pai_v,vP definido 'or uma bus"a em 'rofundidade ro)ulada indu& uma rvore.

Exerccio 1;$.Se(a G um %rafo. 3os)re -ue as se%uin)es afirma!es s2o e-uivalen)es

Qa G * "one#o e KEQGK M KV QGKg 1

Qb KEQGK M KV QGKg 1 e G n2o "on)*m "ir"ui)o.

Q" G * uma rvore

Exerccio 1;+.Tma flores)a * um %rafo a""li"o. ,onsidere uma flores)a! "om n v*r)i"es e m ares)as.

Qa Uual * o nHmero m#imo de v*r)i"es num "om'onen)e "one#o de!W

Qb 3os)re -ue : 'elo menos ma#n g $m,;P v*r)i"es de %rau &ero. Q" 3os)re -ue se m : n*$ en)2o res)a 'elo menos um v*r)i"e de %rau &ero.

14. rvor"s '"ra!oras !" &us)o m#imo "m 'raos &om 0"so #as ar"s)as

Dado um %rafo "one#o "om 'esos nas ares)as G M QV,E, ondeE definimos o &us)o !" um sub'rao" G"omo

O 'roblema no -ual es)aremos in)eressados a 'ar)ir de a%ora * -ual * o "us)o do sub%rafo %erador "one#o de G jmais bara)okW Em ou)ras

'alavras -ueremos de)erminar D EQG )al -ue

Tma rvore %eradora de G de "us)o mnimo )amb*m * ":amada de rvor" '"ra!ora m#ima do %rafo G.

1/.1. E-"r&&ios.

Exerccio 1;/.3os)re -ue se e * uma ares)a de 'eso mnimo em G en)2o e'er)en"e a al%uma rvore %eradora mnima.

Exerccio 1;0.3os)re -ue se e * uma ares)a de 'eso m#imo em G e 'er)en"e a um "ir"ui)o de G en)2o e#is)e uma rvore %eradora mnima de QVQG,EQG eP -ue )amb*m * uma rvore %eradora mnima de G. 3os)re -ue o mesmo vale 'ara )oda ares)a de 'eso m#imo de )odo "ir"ui)o deG.

Exerccio 1;.3os)re -ue 'ara -ual-uer 2 V QG n2ova&io a ares)a de menor "us)o emEQ2,2 )em -ue 'er)en"er a )oda rvore %eradoramnima de G.

Exerccio 1;5.,onsidere a se%uin)e es)ra)*%ia 'ara "om'u)ar uma rvore %eradora de "us)o mnimo dado um %rafo conexo G M QV,E,

man)emos um "on(un)o D Qini"ialmen)e va&io de ares)as e a "ada 'asso es"ol:emos em u, vP E D uma ares)a &oa'ara D onde ares)a &oa'araD si%nifi"a -ue D u,vPP es) "on)ido no "on(un)o de ares)as de al%uma rvore %eradora mnima de G. O ob(e)ivo desse e#er""io e mos)rar -ueno final as ares)as de Dindu&em uma rvore %eradora mnima de G.

AGM(G)

enquanto G[S] no uma rvore geradora faa

descubra uma aresta f boa para S em E(G)\S,

inserir f em S;

devolva S.

Su'on:a -ue sem're e#is)e 'elo menos uma ares)a boa 'ra ser es"ol:ida em "ada i)era2o do enquanto. 6rove -ueparaualuer G conexo,AG3QG constrIi uma >rvore geradora mnima de G. QDi"a use o invarian)e D su&con;unto dealguma >rvore geradora mnima de G an)es de"ada i)era2o do lao.


de /; 11B1$B$;1+ 1;09


29/40

Exerccio 1;7.A%ora o ob(e)ivo * 'rovar a :i'F)ese assumida no e#er""io a"ima de -ue sem're : uma ares)a boa 'ra ser es"ol:ida. 6rove -ue

se uma >rvore geradora mnima de G e D EQ ent(o para todo 2 V QG tal ue o corte EQ2,2 n(o contm arestas de D vale o seguinteQ

uma aresta u,vP de custo mnimo no corteEQ2,2 &oa para D. QDi"a dados G,D, "omo no enun"iado )ome 2 e e EQ2,2 "omo enun"iadoe "onsidere $ "asos se e EQ e se etEQ.

Exerccio 1;9.Se(a G uma rvore %eradora de um %rafo G "om 'eso nas ares)as. 3os)re -ue * uma rvore %eradora mnima se e somen)e se

'ara )oda e EQG EQ o Hni"o "ir"ui)o C de e * )al -ue )odas as ares)as de C "us)am n2o mais -ueQe.

Exerccio 11;.3os)re -ue se 'ara )odo "or)e em G e#is)e uma Hni"a ares)a de "us)o mnimo no "or)e en)2o a rvore %eradora de "us)o mnimo *Hni"a. A re"'ro"a dessa afirma2o valeW Jus)ifi-ue.

Exerccio 111.Se(a G um %rafo "one#o "om 'esos 'osi)ivos nas ares)as. 6ara )odo rvore %eradora mnima e )odo "amin:o+ em + * um"amin:o mnimo em GW

1:. Al'ori)mo !" rusal 0ara rvor" '"ra!ora m#ima

A id*ia do al%ori)mo de ?rus faa se findQu * diferen)e de findQv en)2o insira uv em S


de /; 11B1$B$;1+ 1;09


30/40

unionQuvdevolva S.

Den)re as es)ru)uras de dados mais "on:e"idas 'ara re'resen)ar "on(un)os dis(un)os ":amamos a a)en2o 'ara uma delas a re'resen)a2o 'or flores)a "om uni2o 'or ran4 e bus"a"om "om'ress2o de "amin:os. Essa re'resen)a2o "om as :eurs)i"asmen"ionadas )em um F)imo desem'en:o assin)F)i"o

T"or"ma 2@.% tempo gasto com m opera'Pes num universo com n elementos % QQm nl%Qn.

Deno)amos 'orl%Qn o nHmero de ve&es -ue )emos -ue i)erarl%a)* -ue o valor ob)ido se(a menor ou i%ual a 1 'or e#em'lo l%$1M /.

Nesse "aso o nHmero de o'era!es ma4efind e union no al%ori)mos de ?rus


31/40

Fi'ura 22* Em'arel:amen)o3 M $,/P,0,P .

Uuando um v*r)i"e v'er)en"e a al%uma ares)a e de um em'arel:amen)o3 di&emos -ue v * &ob"r)o'or3. Dessa forma 'ela defini2o deem'arel:amen)o -uando v * "ober)o 'or3 e#is)e uma Hni"a ares)a e EQv 3. Se um em'arel:amen)o "obre V QG en)2o ele * ":amado de"m0ar"lam"#)o 0"r"i)o em G.

h %rafos -ue n2o admi)em em'arel:amen)o 'erfei)o "omo 'or e#em'lo os "ir"ui)os de "om'rimen)o m'ar de fa)o -ual-uerem'arel:amen)o em CM)em no m#imo ares)as lo%o "ir"ui)os de "om'rimen)o 'ar admi)em em'arel:amen)o 'erfei)o mas os de

"om'rimen)o m'ar n2o. No e#em'lo da fi%ura $$o em'arel:amen)o 1, $P, /, 0P, +,P * 'erfei)o assim "omo o em'arel:amen)o 1,$P,

+,0P,/,P .

Tm em'arel:amen)o em G "om o maior nHmero 'ossvel de ares)as * ":amado de "m0ar"lam"#)o m-imo is)o * um em'arel:amen)o"om

Q+0

ares)as.

Exemplo $+.No "aso dos "ir"ui)os CM* f"il ver -ueUQCM M . O mesmo vale 'ara %rafos "om'le)osUQ6n M . No "aso de "amin:os

UQ+$Mg1 MUQ+$M M M'ara )odo M 8 ;.

No es)udo de em'arel:amen)os sur%e um )i'o es'e"ial de "amin:o onde as ares)as al)ernam en)re ares)a do em'arel:amen)o e ares)a fora doem'arel:amen)o. Tm "amin:o+ Mx

1,x

$,,x

4 'ara 4 ^ 1 em G "u(as ares)as al)ernam en)re as ares)as deEQG 3 e as ares)as de3 is)o *

* ":amado de38al)"r#a#)".

Se os v*r)i"es e#)remos do "amin:o3al)ernan)e n(o s2o "ober)os 'or3 en)2o ":amamos esse "amin:o de38aum"#)a#)". ,omo o nomesu%ere a e#is)4n"ia de um "amin:o3aumen)an)e+ em G si%nifi"a -ue 'odemos ob)er um em'arel:amen)o em G "om mais ares)as -ue3. De

fa)o a diferena sim*)ri"a3 EQ+ M Q3 EQ+ Q3 EQ+ * um em'arel:amen)o -ue "obre )odos os v*r)i"es "ober)os 'or3 e ainda "obre ose#)remos de+.

Exemplo $/.Na fi%ura $$)emos3 M $,/P,0,P e o "amin:o3aumen)an)e+ "omEQ+ M 1,$P,$,/P,/,0P,0,P,,+P . A diferena

sim*)ri"a desses "on(un)os *

-ue * um em'arel:amen)o "om uma ares)a a mais -ue3.

O se%uin)e )eorema * uma "ara")eri&a2o de em'arel:amen)o m#imo em fun2o dos "amin:os aumen)an)es. Esse resul)ado * fundamen)al no'ro(e)o de um al%ori)mo efi"ien)e -ue de)ermina em'arel:amen)os m#imos mais adian)e veremos esse al%ori)mo 'ara %rafos bi'ar)idos.

T"or"ma 21 Q@eorema de 8er%e 1905.2m emparelximo se, e somente se, G n(o contmcamin


32/40

X

Res)a 'rovar -ue3 EQ+ * em'arel:amen)o. Su'on:a -ue n2o en)2o e#is)em duas ares)as de3 EQ+ ad(a"en)es di%amos -ue e,f 3

EQ+ "om e f Mx. Dessa formax deve ser um v*r)i"e in)erno em+ 'or)an)o deve es)ar "ober)o 'or uma ares)ag 3 lo%ox e g e ambasares)as es)2o em3 absurdo.

E-"r&&ios.

Exerccio 119.6rove a i%ualdade K3 EQ+K M KQ3 EQ+ QEQ+ 3K usada na demons)ra2o do )eorema de 8er%e.

Exerccio 1$;.De)ermine o nHmero de ares)as num em'arel:amen)o m#imo nos %rafos6n Cn+ne6m,n.

Exerccio 1$1.Se3 * um em'arel:amen)o em um %rafo G -ual-uer e se+ * um "amin:o3aumen)an)e em G mos)re -ue3 EQ+ )amb*m *um em'arel:amen)o.

Exerccio 1$$.6rove -ue uma rvore -ual-uer )em no m#imo um em'arel:amen)o 'erfei)o.

Exerccio 1$+.,onsidere um %rafo -ual-uer G de n v*r)i"es. 3os)re -ue um em'arel:amen)o em G )em no m#imo n*$ ares)as.

Exerccio 1$/.3os)re -ue o 4"ubo admi)e em'arel:amen)o 'erfei)o 'ara )odo 4 ^ $.

Exerccio 1$0.Duas 'essoas (o%am um (o%o sobre um %rafo G al)ernadamen)e sele"ionando v*r)i"es dis)in)os v;, v1, v$,)ais -ue 'ara i 8 ; vi

* ad(a"en)e a vig1

. O Hl)imo (o%ador -ue "onse%uir sele"ionar um v*r)i"e ven"e o (o%o.

3os)re -ue o 'rimeiro (o%ador )em uma es)ra)*%ia 'ara ven"er o (o%o se e somen)e se o %rafo G n2o )em um em'arel:amen)o 'erfei)o.

Exerccio 1$.3os)re -ueUQG M 7QLG Qve(a a defini2o de LG no e#er""io 1.

Exerccio 1$5.6rove -ue se3 * em'arel:amen)o em G en)2o e#is)e um em'arel:amen)o m#imo -ue "obre )odos os v*r)i"es "ober)os 'or3.

Exerccio 1$7.Deno)emos ciQG o nHmero de "om'onen)es "one#os do %rafo G "om um nHmero m'ar de v*r)i"es. 3os)re -ue se G )em um

em'arel:amen)o 'erfei)o en)2o ciQG g D KDK 'ara )odo "on(un)o D de v*r)i"es.

1?. Em0ar"lam"#)os "m 'raos bi0ar)i!os

6or )oda es)a se2o ado)aremos -ue as 'ar)es de v*r)i"es inde'enden)es de um %rafo bi'ar)ido G s2o deno)adas 'orA eB.

Oo )eorema de hall Q19+0 )amb*m "on:e"ido "omo o )eorema do "asamen)o * devido ao ma)em)i"o 6:ili' hall * um resul)ado -ue d uma"ondi2o ne"essria e sufi"ien)e -ue 'ermi)e a sele2o de um elemen)o dis)in)o de "ada um de uma "ole2o de "on(un)os fini)os Se(a D um"on(un)o de "on(un)os fini)os. Tmsistema de representates de D * um "on(un)oX'ro -ual e#is)e uma bi(e2ofX D )al -uex fQx. En)2o Dadmi)e )al sis)ema se e s* se

O )eorema )em mui)as a'li"a!es in)eressan)es. 6or e#em'lo se dividimos um baral:o em 1+ mon)es de / "ar)as "ada en)2o usando o)eorema de "asamen)o 'odemos mos)rar -ue sem're * 'ossvel sele"ionar e#a)amen)e uma "ar)a de "ada 'il:a de modo -ue as 1+ "ar)assele"ionadas "on)4m e#a)amen)e uma "ar)a de "ada valor Q=s $ + rain:a rei. 3ais abs)ra)amen)e se(a G um %ru'o e" sub%ru'o fini)o deG. En)2o o )eorema de "asamen)o 'ode ser usado 'ara mos)rar -ue e#is)e um "on(un)oX )al -ueX * um )an)o 'ara o "on(un)o das "lasses la)erais es-uerda -uan)oa direi)a de" em G.

O se%uin)e resul)ado d a "ondi2o ne"essria e sufi"ien)e 'ara -ue e#is)a um sis)ema de re'resen)an)es rees"ri)o em lin%ua%em de )eoria dos

%rafos.

T"or"ma 22 Q@eorema de hall 19+0.Em todo grafo &ipartido G M QAB,E existe um emparel


33/40

X

emonstra'(o.Se(am G M QA B,E um %rafo bi'ar)ido3 um em'arel:amen)o -ue "obreA e D A. 6ara "adax D deno)e 'or vxo v*r)i"e

deB )al -ue x,vxP3. ,er)amen)e v

x$QD. Ainda sex D e@ D"omx0@ en)2o v

x0v

@ lo%o K$QDK^KDK.

amos 'rovar 'or indu2o em KAK -ue se K$QDK^KDK 'ara )odo D A en)2o e#is)e um em'arel:amen)o -ue "obreA.

Se KAK M 1 en)2o fa"ilmen)e "ons)a)amos -ue e#is)e um em'arel:amen)o -ue "obreA. Se(a G M QAB,E um %rafo bi'ar)ido -ue sa)isfa& Q+ e

su'on:a -ue )odo %rafo bi'ar)ido QAB,E "om KAK : KAK -ue sa)isfa& a "ondi2o de hall Q+ )em um em'arel:amen)o -ue "obreA.

,aso 1 K$GQDK 8 KDK 'ara )odo D A n2ova&io. Es"ol:a uma ares)a a,&PE e "onsidere o %rafo bi'ar)ido G M G g a g & sobreA MA aP e

B MB &P. Nesse "aso 'ara "ada D AA vale -ue K$GQDK^KDK e 'ela :i'F)ese indu)iva "on"lumos -ue e#is)e3 -ue "obreA. 6or)an)o3

a,&PP "obreA.

,aso $ K$QDK M KDK 'ara al%um D A n2ova&io. O %rafo bi'ar)ido indu&ido" M G_D $QD` sa)isfa& a "ondi2o de hall Qos vi&in:os de D em" s2o os mesmo vi&in:os em G e 'ela :i'F)ese indu)iva 'odemos "on"luir -ue e#is)e um em'arel:amen)o3 em" -ue "obre D. A%ora

"onsidere o sub%rafo bi'ar)ido indu&ido1 M G_D$GQD` e su'on:a -ue e#is)aX D)al -ue no %rafo1 vale K$1QXK : KXK. @eremos no %rafo G

"on)rariando a :i'F)ese de G sa)isfa&er a "ondi2o de hall. Assim K$1QXK ^ KXK 'ara )odoX De 'ela :i'F)ese indu)iva e#is)e um

em'arel:amen)o3 em1 -ue "obre D. 6ara "on"luir a demons)ra2o * sufi"ien)e observar -ue3 3* um em'arel:amen)o em G -ue "obreA.

Corolrio 25 Q>orma defe")iva do )eorema de hall.Em todo grafo &ipartido G M QAB,E existe um emparel


34/40

Exerccio 1+9.Se(a G M QA B,E um %rafo bi'ar)ido )al -ue KAK M KBK. Se(a3 a ma)ri& inde#ada 'orA \Be definida 'or3Qu,v M 1 se uv * umaares)a de G e3Qu,v M ; "aso "on)rrio. O 0"rma#"#)" da ma)ri&3* o nHmero

onde a soma se es)ende a )odas as bi(e!es WA B. 3os)re -ue o 'ermanen)e de3 * i%ual ao nHmero de em'arel:amen)os 'erfei)os em G.

17.1. Al'ori)mo !" E!mo#!s.

O al%ori)mo abai#o re"ebe um %rafo bi'ar)ido G M QA B,E e devolve um em'arel:amen)o -ue "obreA ou um sub"on(un)o D A )al -ueK$QDK : KDK "u(a e#is)4n"ia * %aran)ida 'elo )eorema de hall. Assumimos -ue "amin:os3al)ernan)e )4m um e#)remo des"ober)o emA.

A id*ia do al%ori)mo * "ons)ruir "amin:os al)ernan)es a 'ar)ir de um v*r)i"e n2o"ober)o emA. 6or e#em'lo no %rafo da fi%ura abai#o oal%ori)mo "omea 'elo v*r)i"e a

1n2o"ober)o 'or3. O 'rF#imo 'asso * es"ol:er um vi&in:o de a

1. Se e#is)ir al%um vi&in:o n2o "ober)o en)2o

a":amos um "amin:o aumen)an)e "aso "on)rrio uma ares)a de3 in"ide nesse vi&in:o e )emos um "amin:o al)ernan)e no e#em'lo a1,&

1,a

+. O

'rF#imo 'asso * "on)inuar a bus"a a 'ar)ir de um vi&in:o dos v*r)i"es da forma ai( es"ol:idos. No)emos en)re)an)o -ue bas)a bus"ar )ais

vi&in:os den)re os v*r)i"es ainda n2o es"ol:idos no nosso e#em'lo a'Fs o es)%io re'resen)ado 'ela fi%ura Qe abai#o n2o : ne"essidade de"onsiderar a ares)a a

+,&

0P 'ois o novo "amin:o al)ernan)e definido 'or essa ares)a seria redundan)e 'ara nossos 'ro'Fsi)os. No es)%io dado 'ela

fi%ura Qf ":e%amos a um "amin:o aumen)an)e.

Uuando o al%ori)mo des"obre um "amin:o aumen)an)e usao 'ara ob)er um em'arel:amen)o "om mais ares)as e re"omea o 'ro"esso. ,aso"on)rrio )eremos "ons)rudo "amin:os al)ernan)es -ue "omeam num v*r)i"e des"ober)o e )odos )erminam num v*r)i"e "ober)o. Os v*r)i"esdesses "amin:os definem um "on(un)o -ue viola a "ondi2o de hall. 6or e#em'lo na fi%ura abai#o o al%ori)mo "omea 'elo v*r)i"e n2o"ober)oa

/. Esse v*r)i"e )em os vi&in:os &

$e &

+-ue es)2o "ober)os 'elas ares)as a

1&

$e a

+&

+res'e")ivamen)e. O v*r)i"e a

1( )em )odos os seus vi&in:os

es"ol:idos assim "omo a+ e n2o se 'ode mais es)ender os "amin:os. Nesse "aso$Qa

1,a

+,a

/P M &

1,&

$P e a

1,a

+,a

/P* um obs)"ulo 'ara um

em'arel:amen)o "obrirA.

Essa id*ia es) formali&ada na se%ui)e 'rova do )eorema de hall.

Degunda demonstra'(o do eorem de "all.Se(a3 um em'arel:amen)o -ue "obreA e D A. 6ara "adax Ddeno)e 'or vxo v*r)i"e deB )al

-ue x,vxP 3. ,er)amen)e v

x$QD. Aindax D e@ D "omx0@im'li"am em v

x0v

@ lo%o K$QDK^KDK.

A%ora 'ara a re"'ro"a se(am G M QA B,E um %rafo bi'ar)ido )al -ue K$QDK^KDK 'ara )odo D A e3um em'arel:amen)o m#imo em G.Su'on:a -ue3 n2o "obreA e se(a v A n2o "ober)o 'or3. Deno)e 'or Co sub"on(un)o deAB formado 'or )odos os v*r)i"es al"anveis a

'ar)ir de v'or "amin:o3al)ernan)e. @ome D M C A e M C B.

,er)amen)e $QD. A%ora se e#is)ex D "om um vi&in:o fora de di%amos@ B en)2ox e@ s2o li%ados 'or um "amin:o3aumen)an)e "on)rariando o fa)o de3 se m#imo 'or)an)o M$QD e KK M K$QDK.

,omo e D gvP s2o "ober)os 'or3 Q(us)ifi-ue )emos KK M KDKg 1 lo%o K$QDK M KDKg 1 : KDK o -ue "on)raria a :i'F)ese sobre G lo%o3 "obreA.

Em lin%ua%em de al%ori)mos

Edmonds


de /; 11B1$B$;1+ 1;09


35/40

2: existe no coberto por

;

;

devolva ;

7:

devolva S;

escolha ;

existe tal que

insere em ;

insere em ;

volte para 7;

caminho -aumentante de at ;

;

volte para 2;

A "orre2o do al%ori)mo se%ue da )er"eira 'rova do )eorema de hall.

An>lise da complexidade.O )em'o 'ara a bus"a de um "amin:o3aumen)an)e * %QKV K KEK Quma bus"a no 'ior "aso. >a&endo uma bus"a 'ra"ada v*r)i"e resul)a em %QKV KQKV K KEK.

E-"r&&ios.

Exerccio 1/;.Refaa os e#er""ios $e 17.

Exerccio 1/1.Tma es"ola se"undria abriu va%as 'ara "on)ra)a2o de do"en)es 'ara as se%uin)es reas 3a)em)i"a Uumi"a >si"a 8iolo%ia6si"olo%ia e E"olo%ia. 6ara -ue umQa "andida)oQa se ins"reva eleQa deve informar a rea em -ue se %raduou e as reas "orrela)as em -ue sesen)e von)ade 'ara le"ionar. A es"ola re"ebeu seis ins"ri!es 'ara es)as 'osi!es da se%uin)e maneira

Ca#!i!a)o r"as3a)em. Uumi"a >si"a 8iol. 6si"ol. E"ol.

An)cnio \ \8ernardo \ \ \ \,ssia \ \ \D*bora \ \ \ \

Evandro \ \>ernanda \ \

E#e"u)e um al%ori)mo "on:e"ido -ue de)ermine o maior nHmero de 'rofessores -ue a es"ola 'ode "on)ra)ar.

Exerccio 1/$.>aa uma anlise de)al:ada da "om'le#idade do al%ori)mo de Edmonds.

Exerccio 1/+.3odifi-ue o al%ori)mo EdmondsQA8E 'ara -ue ele devolva um em'arel:amen)o m#imo.

Exerccio 1//.Se(aB um %rafo bi'ar)ido "om bi'ar)i2oA,B. ,ons)rua um %rafo orien)ado a 'ar)ir deBorien)ando as ares)as no sen)ido deX'ara Y . A%ora a"res"en)e aos v*r)i"es de dois novos v*r)i"ess e t "oms li%ado a )odos os v*r)i"es deX no sen)ido des'araX e "om t li%adoa )odos os v*r)i"es de Y no sen)ido de Y'ara t.

Su'on:a -ue esse %rafo orien)ado -ue vo"4 "ons)ruiu modela uma rede de "om'u)adores onde "ada ares)a )em a "a'a"idade de 1 unidadede )ransmiss2o. 3os)re -ue o flu#o m#imo des'ara t * i%ual ao nHmero m#imo de ares)as num em'arel:amen)o emB.

19. Cob"r)ura

Tma &ob"r)ura 0or v(r)i&"s em um %rafo G * um sub"on(un)o 2 V QG )al -ue e20'ara )oda ares)a e E ou se(a )oda ares)a de Gen"on)ra 2.

Exemplo $0.No e#em'lo da fi%ura abai#o )emos o dia%rama de um %rafo bi'ar)ido as ares)as em des)a-ue definem um em'arel:amen)o3. Osub"on(un)o de v*r)i"es a

1,a

$,&

+,&

/P* uma "ober)ura 'ois todas as ares)as do %rafo in"idem em 'elo menos um desses v*r)i"es.


de /; 11B1$B$;1+ 1;09


36/40

X

X

Tma &ob"r)ura m#ima * uma "ober)ura "om o menor nHmero 'ossvel de v*r)i"es -ue * deno)ado 'or QG

Q+7

T"or"ma 24 Q@eorema de ?wni% 19+1.$um grafo &ipartido G M QA B,E o taman


37/40

Tm %rafo G -ue "on)*m "ir"ui)o :amil)oniano * ":amado 'rao amil)o#ia#o.

Tma "ondi2o ne"essria 'ara um %rafo ser :amil)oniano * -ue a remo2o de um sub"on(un)o de v*r)i"es resul)a num nHmero limi)ado de"om'onen)es "one#as.

ro0osi$o 2:.De G


38/40

Exerccio 1/7.3os)re -ue o n"ubo * :amil)oniano.

Exerccio 1/9.Tm &ami#o amil)o#ia#o em G * um "amin:o -ue 'assa 'or )odos os v*r)i"es de G. 3os)re -ue se G "on)*m um "amin:o:amil)oniano en)2o cQG g D KDK 1 'ara )odo sub"on(un)o 'rF'rio de v*r)i"es D.

Exerccio 10;.6rove -ue se G * )al -ue )odo 'ar de v*r)i"es u,v n2oad(a"en)es vale dQu dQv ^KV QGKg 1 en)2o G "on)*m um "amin:o:amil)oniano.

Exerccio 101.6rove dQu dQv ^KV QGK 'ara )odo 'ar u,v de v*r)i"es n2o ad(a"en)es en)2o G :amil)oniano se e somen)e se G uv:amil)oniano.

Exerccio 10$.D4 um e#em'lo de %rafo "om n v*r)i"es %rau mnimo e n2o:amil)oniano.

Exerccio 10+.Su'on:a -ue e#is)e um al%ori)mo QG,u,v -ue de)ermina em )em'o 'olinomial um Qu v"amin:o mnimo no %rafo diri%ido"om 'esos reais nas ares)as G. 3os)re "omo usar esse al%ori)mo 'ara de)erminar se G )em um "ir"ui)o Qorien)ado :amil)oniano em )em'o

'olinomial. QicaQ a)ribua 'eso g1 a )odas as ares)as do %rafo e "om'u)e QG,u,v 'ara )odo Qv,u EQG.

Exerccio 10/.Observamos -ue o 'roblema de de)erminar se um %rafo * :amil)oniano * N6"om'le)o 'or)an)o a e#is)4n"ia de uma al%ori)mo"omo a"ima es)abele"e -ue 6MN6.

21. Trilas "ul"ria#as

'ossvel desen:ar a fi%ura abai#o sem )irar o l'is do 'a'el e sem re'e)ir nen:um )raoW

amos reformular essa 'er%un)a na )erminolo%ia de @eoria dos Grafos. Di&emos -ue num %rafo G M QV,E uma se-4n"ia al)ernada v*r)i"eqares)aqv*r)i"e -ue n2o re'e)e ares)as

Q//

"om eiM vig1,viPE 'ara )odo i 1,$,,4P e ei0e;'ara )odo i0; * ":amada de )rila.

Fi'ura 24* E#em'lo 1a$&+c/d$ e /d$&+c/e0f+ s2o )ril:as no %rafo.

Se em Q// )emos v;M v

4 en)2o di&emos -ue a )ril:a * uma )rila "&a!a.

Tma )ril:a -ue 'assa 'or )odas as ares)as do %rafo * ":amada de )rila "ul"ria#a e uma )ril:a fe":ada -ue 'assa 'or )odas as ares)as do %rafo* ":amada de )rila "ul"ria#a "&a!a.

Tm %rafo -ue "on)en:a uma )ril:a euleriana fe":ada * di)o 'rao "ul"ria#o.

T"or"ma 2< Q@eorema de Euler 15+0.2m grafo conexo euleriano se, e somente se, todo vrtice tem graupar.

emonstra'(o.Se um %rafo "one#o * euleriano en)2o um v*r)i"e -ue o"orre 4 ve&es na )ril:a euleriana fe":ada )em %rau $4.

6or ou)ro lado su'on:a -ue um %rafo "one#o )em )odos os seus v*r)i"e de %rau 'ar. Se(a M v;e

1v

1v

Mg1e

Mv

Muma )ril:a "om o maior nHmero

'ossvel de ares)as. ,omo )odos os v*r)i"es )4m %rau 'ar e a )ril:a "on)*m )odas as ares)as -ue in"idem nos v*r)i"es dos e#)remos da )ril:a


de /; 11B1$B$;1+ 1;09


39/40

)emos -ue v;M v

M.

A%ora su'on:a -ue e * uma ares)a -ue n2o a'are"e na )ril:a. No)e -ue 'odemos assumir e M uvi'ara al%um v

i 'ois o %rafo * "one#o.

3as isso im'li"a -ue uevie

i1e

Mv

Me

1v

1e

ig1v

i* uma )ril:a "om mais ares)as -ue . 6or)an)o 'assa 'or )odas as ares)as do %rafo.

E-"r&&ios

Exerccio 100.3os)re -ue se G )em no m#imo dois v*r)i"es de %rau m'ar en)2o "on)em uma )ril:a euleriana.

Exerccio 10.3os)re -ue se G * euleriano en)2o LG Qve(a e#er""io 1$.1 na '%ina 1+ 'ara a defini2o de LG * euleriano.

Exerccio 105.3os)re -ue se G * euleriano en)2o LG * :amil)oniano.

D4 um e#em'lo onde a re"'ro"a n2o vale.

Exerccio 107.Tm %rafo euleriano 'ode )er uma ares)a de "or)eW

Exerccio 109.6rove -ue um %rafo "one#o * euleriano se 'ode ser 'ar)i"ionado em "ir"ui)os ares)adis(un)os.

Exerccio 1;.O "aso * a for)una do bilionrio 8ob Le2o 3arin:o. Ele foi assassinado em sua mans2o e Ed 3or) o de)e)ive in)erna"ionalmen)e"on:e"ido -ue nas :oras va%as es)uda @eoria dos Grafos foi ":amado 'ara inves)i%a2o. O mordomo afirma -ue viu o fa#ineiro en)rar no sal2oda 'is"ina Qonde a"on)e"eu o assassina)o e en)2o lo%o em se%uida saiu do sal2o da 'is"ina 'ela mesma 'or)a. O fa#ineiro en)re)an)o di& -ue elen2o 'ode ser o :omem -ue o mordomo ale%a )er vis)o ( -ue ele en)rou na mans2o 'or uma das 'or)as do sal2o da 'is"ina a)ravessou "adaa'osen)o 'assando 'or "ada "ada 'or)a da mans2o e#a)amen)e uma ve& e dei#ou a "asa 'ela ou)ra 'or)a do sal2o da 'is"ina. Ed 3or) verifi"a a

'lan)a da "asa Qve(a fi%ura abai#o. Den)ro de al%umas :oras ele de"lara o "aso resolvido. Uuem vo"4 a"redi)a )er ma)ado 8ob Le2o 3arin:oW

Exerccio 11.O al%ori)mo de >leur de 177+ des"obre uma )ril:a euleriana fe":ada se o %rafo dado for euleriano.

Fleury

escolha ;

insira no final de ;

escolha e, se for possvel, de forma que tenha o mesmo nmero de componentes conexos que ;

;

.

6rove -ue se G * euleriano en)2o a )ril:a definida 'ela se-4n"ia v*r)i"es ad(a"en)es D M u1,u

$,,u

M"ons)ruda 'elo al%ori)mo * euleriana.

De)ermine a "om'le#idade do al%ori)mo.

Exerccio 1$.A fi%ura abai#o mos)ra a 'lan)a da ,asa dos Es'el:os um labirin)o em um 'ar-ue de divers!es -ue fun"iona de forma inusi)adade'ois -ue um visi)an)e 'assa 'or uma 'or)a ela * au)oma)i"amen)e )ran"ada. ,onsiderando -ue )odas as 'or)as es)2o ini"ialmen)e aber)asde)ermine se * sem're 'ossvel es"a'ar da ,asa dos Es'el:os ou se al%u*m 'ode fi"ar )ran"afiado 'ara sem're em al%um -uar)o. Se es)e 'eri%ofor real e#e"u)e um al%ori)mo -ue a(uda a 'ro(e)ar um brin-uedo mais se%uro mos)rando -ue :aver sem're a 'ossibilidade de es"a'ar da ,asados Es'el:os. o"4 'ode al)erar a 'lan)a de a"ordo "om o al%ori)mo e deve mos)rar um 'er"urso "om'le)o nes)a nova 'lan)a em -ue um visi)an)e

'ode es"a'ar da ,asa dos Es'el:os de forma se%ura. QDi"a n2o modele "ada 'or)a da "asa "omo um v*r)i"e de um %rafo.


de /; 11B1$B$;1+ 1;09


40/40


Documents

BC1429 — Teoria Dos Grafos