Teoria de Grafos 1

7/25/2019 Teoria de Grafos 1

1/124

Teora de Grafos


2/124

CONCEPTO La teora de grafos(tambin

llamada teora de las grcas) es uncampo de estudio de las matemticas ylas ciencias de la computacin, que

estudia las popiedades de los!a"os (tambin llamadas grfcas) queson estuctuas que constan de dospates, el con#unto de VERTICES, nodoso puntos$ y el con#unto de ARISTAS,l%neas o lados que pueden seoientados o no&


3/124

Denicin

Grafo:un !a"o es un con#unto, no 'ac%o,de ob#etos llamados nodos (o 'tices) yuna seleccin de paes de nodos,llamados e#es (o aistas) donde estos

pueden se oientados o no&n !a"o G = (V!", dondeV es un

con#unto nodos y !es un subcon#unto

del con#unto de paes no odenados deelementos distintos de V&


4/124

e*nicin

#odos $ V%rtices+ constituyen losob#etos de la situacin a epesenta&E#emplo+ - ./,0,C,,E1

E&es $ Aristas $Arcos+ con"oman laselaciones ente un pa de ob#etosepesentados po los nodos&

E#emplo+ 2 - .(/,0),(/,C),(0,C),(0,E),(C,),(,E)1

Tanto los nodos como e#es, pueden teneatibutos cuantitati'os y3o cualitati'os('aiables de cualquie tipo)&


5/124

E#emplos


6/124

4a"o simple+

5ulti!a"o+

Pseudo!a"o+

4a"o dii!ido+

Tipos+


7/124


8/124

Eti'etado)istincin que se 6ace a los 'ticesy3o aistas mediante una maca que los 6aceun%'ocamente distin!uibles del esto, es deci,asi!nale a cada 'tice o aista un nombe&

Teminolo!%a+

Ad*acencia)7e dice que dos 'tices sonadyacentes si 6ay una aista que los conecteente ellos&

Grado de n +%rtice)El !ado de un 'tice esun n8meo natual de 9 al in*nito que desi!na eln8meo de aistas le conectan con otos 'tices&


9/124

Incidencia)na aista es incidente a un 'ticesi sta lo une a oto&

,onderacin)Coesponde a una "uncin que a

cada aista le asocia un 'alo (costo, peso,lon!itud, etc&), paa aumenta la e:pesi'idad delmodelo&

Ca-ino)n camino es una secuencia de aistasque comien;an en un 'tice del !a"o y ecoenpate o la totalidad del !a"o conectando 'ticesadyacentes&


10/124

Circito)Cuando e:iste un camino que empie;a

y acaba en el mismo 'tice&

Iso-ors-o)7i dos !a"os son isomo"os slo

'a%a la apaiencia, es deci, que se mantienenlas adyacencias, estuctua, caminos, ciclos,n8meo de 'tices y n8meo de aistas&

Cone.o)n !a"o es cone:o si tiene una 8nicacomponente cone:a, es deci, todos los 'ticesdel !a"o estn elacionados&


11/124

4a"o e!ula+

4a"o completo+

4a"o complementaio+

4a"o bipatito+

4a"o bipatito completo+

Grafo original Grafo complementario


12/124

=boles+

n bol es un !a"ocone:o y sin ciclos ola;os, es deci, un !a"osimple&


13/124

Teminolo!%a+

/os'e)n bol es consideado un bosque sisus componentes cone:as son boles&

0r1ol generador)n bol !eneado de un

!a"o cone:o es un sub!a"o cone:o con el menon8meo posible de aistas y con todos los 'ticesdel !a"o oi!inal& No tiene poque se 8nico&

0r1ol generador -ni-o)El bol !eneadom%nimo es un bol !eneado constuido sobeun !a"o cone:o pondeado con un citeio deseleccin de aistas de*nido po su meno peso&


14/124

Ra2)n bol con a%; es un bol en el que unode sus 'tices 6a sido desi!nado como la a%; y

todas las aistas estn colocadas ale#ndose dedic6a a%;&

,adre)7e considea pade de un 'tice al

'tice adyacente supeio&

3i&o)7e considean 6i#os de un 'tice a todoslos 'tices comunicados po una aista y

adyacentes&

3o&a)7on los 'tices que no tienen 6i#os&


15/124

E.4licacin del -odelo:

Paa inde:a los sitios de la ed de>ntenet, buscadoes como 4oo!le, ?otbot

y Lycos e:ploan sistemticamente la @edcomen;ando en sitios conocidos& Estosbuscadoes utili;a los contenidos& LasaaAas Beb utili;an tanto la b8squeda enanc6ua como en po"undidad paa cea%ndices&


16/124

E#emplo de b8squeda en po"undidad patiendodel si!uiente !a"o e:plicaemos una b8squeda

en po"undidad+a b c d

e f g h

li j k

Ele!imos empe;a po el 'tice a paa manteneun oden al"abtico, pod%a empe;ase pocualquie 'tice del bol en este caso, en otobol en el que la a%; "uea ms claa debe%a se

el 'tice a%; el pimeo&


17/124

7i!uiendo las aistas dii!idas de a nosencontamos con los si!uientes caminos+ )(a,b,c,!) y (a,b,",e) lo que nos da como esultado

el si!uiente bol+a

b

c

g

f

e

e ala aista dii!ida nos lle'a a1, de 1, tenemos dos caminos,

esco!emos pimeo po odenal"abtico i a c y de este 'ticea g$ como no tenemos mscaminos, 'ol'emos a 1ycontinuamos de 1a fy de fa e&

Nue'amente no tenemos podonde se!ui& Esta pate estcompleta&


18/124

/6oa ele!imos el 'tice d, nue'amente pooden al"abtico paa continua nuestab8squeda& El camino esultante es (d,6,l,D,#)&

d

h

l

k

j

Esta 'e; es muc6o ms sencillo

enconta el camino, de da 5, de5a l, de la 6y de 6a&&

El 8nico 'tice no eco!ido po nuestos dos boleses i, paa este esultado de una b8squeda losboles son los mostados$ una b8squeda quecomen;aa en oto 'tice da%a lu!a a otos

boles&

j


19/124

19

@epesentacin de 4a"osii!idos

na epesentacin com8n paa un !a"odii!ido G- (V,A) es la -atri2 de ad*acencia& La mati; de adyacencia paa Ges una mati;A

de dimensin n: n, de elementos booleanos,

dondeAi,jF es 'edadeo si y slo si e:iste unaco que 'aya del 'tice ialj& Con "ecuencia se e:6ibin matices adyacencias

con paa 'edadeo y 9 paa "also&


20/124

20

@epesentacin de 4a"os ii!idos(cont&)

Ota epesentacin, elacionada con laanteio, paa un !a"o dii!ido G- (V,A) es

la -atri2 de ad*acencia eti'etada& La mati; de adyacencia etiquetada paa G

es una mati;Ade dimensin n: n, dondeAi,jF es la etiqueta del aco que 'a del

'tice ialj& 7i no e:iste un aco de iajdebe emplease

como entada paaAi,jF un 'alo que no puedase una etiqueta 'lida&


21/124

21


La 'enta#a de usa una mati; de adyacencia es que eltiempo de acceso equeido a un elemento esindependiente del tamaAo de VyA&

La des'enta#a de usa una mati; de adyacencia esque equiee un espacio (nG) aun si el !a"o tienemenos de nGacos& 7lo lee o e:amina la mati; puede lle'a un tiempo O(nG)&

Paa e'ita esta des'enta#a, se puede utili;a otaepesentacin com8n paa un !a"o dii!ido G- (V,A)llamada epesentacin con lista de ad*acencia&


22/124

22


La lista de adyacencia paa un 'tice ies una lista,en al!8n oden, de todos los 'tices adyacentes a i& 7e puede epesenta Gpo medio de un ae!lo C/0EH/,

donde C/0EH/iF es un apuntado a la lista de adyacenciadel 'tice i&

La epesentacin con lista de adyacencia de un !a"odii!ido equiee un espacio popocional a la sumadel n8meo de 'tices ms el n8meo de acos& 7e usa bastante cuando el n8meo de acos es muc6o

meno que nG& na des'enta#a potencial es que puede lle'a un tiempo

O(n) detemina si e:iste un aco del 'tice ial 'ticej&


23/124

23



24/124

4a"os No ii!idos

Pate de la teminolo!%a paa !a"os dii!idos esaplicable a los no dii!idos&

n grafo no dirigidoGconsiste en un con#unto*nito de 'tices Vy un con#unto de aistasAG

- (V,A)& Los +%rticesse denominan tambin nodoso 4ntos& Las aristas es un pa no odenado de 'tices$ la aista

(v,w) - (w,v)

Los 'tices vy wson ad*acentessi es una aista(v,w)& 7e dice que la aista (v,w) es incidentesobe los

'tices vy w&

24


25/124

4a"os No ii!idos (cont&)

n ca-inoen un !a"o no dii!ido es unasecuencia de 'tices v, vG, I, vn, tal que(v,viJ) es una aista paa K i n&

n ca-ino si-4lees un camino en dondetodos los 'tices, e:cepto tal 'e; el pimeoy el 8ltimo, son distintos&

La longitd del camino es nM , el n8meo

de aistas a lo la!o del camino& n !a"o es cone.osi todos sus paes de

'tices estn conectados&

25


26/124


7ea G- (V,A) un !a"o con con#unto de'tices Vy con#unto de aistasA& ns1grafode Ges un !a"o G- (V,A)

donde+ V es un subcon#unto de V&A consta de las aistas (v,w) enAtales que ' y

B estn en V&

7iA consta de todas las aistas (v,w) enA,tal que vy westn en V, entonces Gseconoce como un s1grafo indcidode G&

26


27/124

27


En el !a"o G- (V,A), donde V-.a,b,c,d1 yA- .(a,b),(a,c), (b,c),

(b,d),(c,d)1, y uno de sus sub!a"osinducidos G de*nido po el con#untode 'tices V - .a,b,c1 yA- .(a,b),

(b,d)1&


28/124


n co-4onente cone.ode un !a"o Gesun sub!a"o cone:o inducido ma:imal, esdeci, un sub!a"o cone:o inducido que po

s% mismo no es un sub!a"o popio denin!8n oto sub!a"o cone:o de G& El !a"o no dii!ido anteio es un !a"o

cone:o que tiene slo un componente

cone:o, y es l mismo& El si!uiente !a"o no dii!ido tiene dos

componentes cone:os&

28


29/124


n ciclo si-4le de un !a"o Ges un caminosimple de lon!itud mayo o i!ual a , queconecta un 'tice consi!o mismo& No se considean ciclos los caminos de la "oma v

(camino de lon!itud 9), v,v(camino de lon!itud ),o v,w,v(camino de lon!itud G)&

n grafo cclicocontiene po lo menos unciclo&

n grafo acclicoal!unas 'eces se conocecomo r1ol li1re& El !a"o anteio muesta dos boles libes&

29


30/124


Los boles libes tienen dospopiedades impotantes+Todo bol libe con n 'tices

contiene e:actamente nM aistas& 7i se a!e!a cualquie aista a un bol

libe, esulta un ciclo&

30


31/124

31

@epesentacin de 4a"os Noii!idos

Los mtodos de epesentacin de !a"os dii!idosse pueden emplea paa epesenta los nodii!idos& na aista no dii!ida ente vy wse epesenta

simplemente con dos aistas dii!idas, una de va w, yota de wa v&

Los mtodos son+

na epesentacin con -atri2 de ad*acencia& Estamati; es simtica& na epesentacin con -atri2 de ad*acencia

eti'etada& Esta mati; es simtica& na epesentacin con lista de ad*acencia&


32/124

32

@epesentacin de 4a"os Noii!idos (cont&)


33/124

/l!oitmos de 4a"osii!idos

/l!oitmos de deteminacin de loscaminos ms cotos+ /l!oitmo de i#Dsta& /l!oitmo de


34/124

/l!oitmos de 4a"os ii!idos M/l!oitmo de i#Dsta

El al!oitmo de i#Dsta, tambinllamado algorit-o de ca-inos-ni-os, es un al!oitmo paa la

deteminacin del camino ms cotodado un 'tice oi!en al esto de'tices en un !a"o dii!ido y con

pesos en cada aco& 7u nombe se e*ee a Eds!e

i#Dsta, quien lo descibi po

pimea 'e; en SS&34


35/124

/l!oitmos de 4a"os ii!idos M/l!oitmo de i#Dsta (cont&)

La idea subyacente en este al!oitmo consisteen i e:ploando todos los caminos ms cotosque paten del 'tice oi!en y que lle'an atodos los dems 'tices&

Cuando se obtiene el camino ms coto desde el'tice oi!en, al esto de 'tices quecomponen el !a"o, el al!oitmo se detiene&

El al!oitmo es una especiali;acin de lab8squeda de costo uni"ome, y como tal, no"unciona en !a"os con aistas de costo ne!ati'o&

35


36/124


escipcin detallada+ 7ea G-(V,A) un !a"o dii!ido y etiquetado& 7ean los 'tices aVyzV$ aes el 'tice de

oi!en yzel 'tice de destino&

7ea un con#unto C, que contiene los 'tices de Vcuyo camino ms coto desde atoda'%a no se conoce& 7ea un 'ecto D, con tantas dimensiones como

elementos tiene V, y que U!uadaV las distanciasente ay cada uno de los 'tices de V&

7ea, *nalmente, oto 'ecto, P, con las mismasdimensiones que D, y que conse'a la in"omacinsobe qu 'tice pecede a cada uno de los 'ticesen el camino&

36


37/124


escipcin detallada+ El al!oitmo paa detemina el camino de lon!itud

m%nima ente los 'tices ayzes+ CV&

& Paa todo 'tice iC, iW a, se establece iX $ a9&G& Paa todo 'tice iCse establece Pi- a.& 7e obtiene el 'tice sCtal que no e:iste oto 'tice

wY Ctal que w s. 7i s-zentonces se 6a teminado el al!oitmo&

Z& 7e elimina de Cel 'tice s+ C C[.s1&& Paa cada aista eYAde lon!itud l, que une el 'ticescon al!8n oto 'tice Y C, 7i l J s , entonces+

7e establece l J s& 7e establece Ps.

\& 7e e!esa al paso Z&37


38/124


/l temina este al!oitmo, en zesta!uadada la distancia m%nima ente ayz&

Po oto lado, mediante el 'ecto Pse puede

obtene el camino m%nimo+ en Pzesta!

, el'tice que pecede azen el camino m%nimo$en P!esta el que pecede a!, y as%sucesi'amente, 6asta lle!a a "#$ADO D""%&AC"&

/plicacin Reb del al!oitmo+ 6ttp+33neo&lcc&uma&es3e'itual3cdd3applets3distanci

a]G9cota3E:ampleG&6tml&

38
http://neo.lcc.uma.es/evirtual/cdd/applets/distancia%20corta/Example2.htmlhttp://neo.lcc.uma.es/evirtual/cdd/applets/distancia%20corta/Example2.htmlhttp://neo.lcc.uma.es/evirtual/cdd/applets/distancia%20corta/Example2.htmlhttp://neo.lcc.uma.es/evirtual/cdd/applets/distancia%20corta/Example2.html


39/124


E#emplo+ Enconta los caminos ms cotos ente

el 'tice y todos los dems del

si!uiente !a"o dii!ido&

39


40/124


>teacin # w DGF DF DZF DF

>nicial .1 QQQ 9 9 99

40


41/124




.,G1 G 9 \9 9 99

41


42/124




.,G1 G 9 \9 9 99

G .,G,Z1 Z 9 9 9 S9

42


43/124




.,G1 G 9 \9 9 99

G .,G,Z1 Z 9 9 9 S9 .,G,Z,1 9 9 9 \9

43


44/124




.,G1 G 9 \9 9 99

G .,G,Z1 Z 9 9 9 S9 .,G,Z,1 9 9 9 \9

Z.,G,Z,,

1 9 9 9 \9

44


45/124


Pseudocdi!o del al!oitmo+

45


46/124

/l!oitmos de 4a"os ii!idos M/l!oitmo de


47/124



48/124



49/124



50/124



51/124



52/124



53/124



54/124



55/124



56/124



57/124



58/124



59/124



60/124



61/124



62/124



63/124



64/124



65/124

/l!oitmos de 4a"os ii!idos M/l!oitmo de 08squeda en /nc6ua

/s'eda en anc5ra(*#o read+,frs searc+en in!ls) es un al!oitmo paa ecoe o buscaelementos en un !a"o (usado "ecuentemente

sobe boles)& >ntuiti'amente, se comien;a en la a%; (eli!iendo al!8n

nodo como elemento a%; en el caso de un !a"o) y see:ploan todos los 'ecinos de este nodo&

/ continuacin paa cada uno de los 'ecinos se e:ploan

sus especti'os 'ecinos adyacentes, y as% 6asta que seecoa todo el bol& 7u nombe se debe a que e:pande uni"omemente

la "ontea ente lo descubieto y lo no descubieto&Lle!a a los nodos de distancia (, slo tas 6abe

lle!ado a todos los nodos a distancia (Q&65

/l it d 4 " i i id


66/124

/l!oitmos de 4a"os ii!idos M/l!oitmo de 08squeda en /nc6ua (cont&)


67/124


escipcin detallada+ ado un 'tice "uente s, se e:ploa los 'tices

de Gpaa UdescubiV todos los 'ticesalcan;ables desde s&

7e busca desde sa todos los 'tices alcan;ables& espus poduce un bol /7con a%; en sy que

contiene a todos los 'tices alcan;ables& El camino desde sa cada 'tice en este ecoido

contiene el m%nimo n8meo de 'tices& Es elcamino ms coto medido en n8meo de 'tices&

67

/l!oitmos de 4a"os ii!idos


68/124


uante un ecoido en anc6ua,cuando se ecoen cietos acos,

lle'an a 'tices sin 'isita& Los acos que lle'an a 'tices

nue'os se conocen como arcos de

r1oly "oman un 1os'ea1arcador en anc5rapaa el !a"odii!ido dado&

68



69/124


/dems de los acos de bol, e:isten dostipos de acos de*nidos po una b8squeda

en anc6ua de un !a"o dii!ido, que seconocen como+ Arco de retroceso:Es el aco que 'a de un

'tice a uno de sus antecesoes& n aco que

'a de un 'tice 6acia si mismo se consideaun aco de etoceso& Arco cr2ado:Es el aco que 'a de un 'tice

a oto que no es ni anteceso ni descendiente&

69



70/124


E#emplo+ @eali;a el ecoido en anc6ua (si!a el

oden al"abtico) y enconta el bosque

abacado del si!uiente !a"o dii!ido&

70



71/124


71


72/124


Pseudocdi!o delal!oitmo+

72



73/124

/l!oitmos de 4a"os ii!idos M/l!oitmo de 08squeda en Po"undidad

n recorrido en 4rofndidad(en in!ls D7SQDe-+ *irs #earc+) es un al!oitmo que pemiteecoe todos los nodos de un !a"o o bol de

manea odenada, peo no uni"ome& 7u "uncionamiento consiste en i e:pandiendo

todos y cada uno de los nodos que 'a locali;ando,de "oma ecuente, en un camino conceto&

Cuando ya no quedan ms nodos que 'isita endic6o camino, e!esa, de modo que epite elmismo poceso con cada uno de los 6emanos delnodo ya pocesado&

73

ii!idos M


74/124

ii!idos /l!oitmo de 08squeda en

Po"undidad (cont&) /cos


75/124

ii!idos /l!oitmo de 08squeda en

Po"undidad (cont&) uante un ecoido en po"undidad,

cuando se ecoen cietos acos,

lle'an a 'tices sin 'isita& Los acos que lle'an a 'tices

nue'os se conocen como arcos de

r1oly "oman un 1os'ea1arcador en 4rofndidad paa el!a"o dii!ido dado&

75



76/124

/l!oitmos de 4a"os ii!idos M/l!oitmo de 08squeda en Po"undidad (cont&)

/dems de los acos de bol, e:isten tes tiposde acos de*nidos po una b8squeda enpo"undidad de un !a"o dii!ido, que se conocen

como+ Arco de retroceso:Es el aco que 'a de un 'tice a

uno de sus antecesoes& n aco que 'a de un 'tice6acia si mismo se considea un aco de etoceso&

Arco de a+ance:Es el aco que 'a de un 'tice auno de sus descendientes& Arco cr2ado:Es el aco que 'a de un 'tice a oto

que no es ni anteceso ni descendiente&

76



77/124


E#emplo+ @eali;a el ecoido en po"undidad

(si!a el oden al"abtico) y enconta el

bosque abacado del si!uiente !a"odii!ido&

77



78/124


78



79/124



79

/l!oitmos de 4a"os No


80/124

/l!oitmos de 4a"os Noii!idos

/l!oitmos de deteminacin de los caminosms cotos+ /l!oitmo del camino ms coto&

/l!oitmos de boles abacadoes de costom%nimo+ /l!oitmo de Pim& /l!oitmo de _usDal&

/l!oitmos de ecoido o b8squeda+ /l!oitmo de b8squeda en anc6ua& /l!oitmo de b8squeda en po"undidad& 0osques abacadoes&

80

/l!oitmos de 4a"os No ii!idos M


81/124

/l!oitmos de 4a"os No ii!idos /l!oitmo del Camino 5s Coto

Este al!oitmo busca el camino ms coto ente dos'tices&

@ecibe como entada el !a"o no dii!ido G, el 'tice

inicial y el 'tice *nal& El al!oitmo es el si!uiente+

3. DaF - 9, si4W aD4F - & 7e tiene el con#unto de'tices $&

G& 7iz$temina y DzF es la distancia ms cota ente ay

z&& Esco#a v$donde DvF es el 'alo m%nimo& $- $M .v1&Z& 7i4$y es adyacente a vD4F - min.D4F,DvFJc(v,4)1&& Pase al paso G&

81



82/124

/l!oitmos de 4a"os No ii!idos /l!oitmo del Camino 5s Coto (cont&)

E#emplo+ Enconta el camino ms coto ente los

'tices ay +&

82



83/124


83

=

==

=

=

=

=

=

=

][

][

][

][

][

][

][

0][

$%%%%%%%&

hD

gD

fD

eD

dD

cD

bD

aD

hgfedcbaT



84/124


84

=

==

=

=

=

=

=

=

][

][

1][

][

][

][

2][

0][

$%%%%%%&

hD

gD

fD

eD

dD

cD

bD

aD

hgfedcbT

=+=

=+=

1$10%min&][

2$20%min&][a

fD

bDaAdyacente



85/124


85

=

==

=

=

=

=

=

=

][

6][

1][

][

4][

][

2][

0][

$%%%%%&

hD

gD

fD

eD

dD

cD

bD

aD

hgedcbT

=+=

=+=

6$51%min&][

4$31%min&][a

gD

dDfAdyacente



86/124


86

=

==

=

=

=

=

=

=

][

6][

1][

6][

4][

4][

2][

0][

$%%%%&

hD

gD

fD

eD

dD

cD

bD

aD

hgedcT

=+=

=+=

=+=

6$42%min&][

4$22%4min&][

4$22%min&][

a

eD

dD

cD

bAdyacente



87/124


87

5][

6][

1][

6][

4][

4][

2][

0][

$%%%&

=

==

=

=

=

=

=

=

hD

gD

fD

eD

dD

cD

bD

aD

hgedT

=+=

=+=

5$14%min&][

6$34%6min&][a

hD

eDcAdyacente



88/124


88

5][

6][

1][

6][

4][

4][

2][

0][

$%%&

=

==

=

=

=

=

=

=

hD

gD

fD

eD

dD

cD

bD

aD

hgeT

{ 6$44%6min&][a =+=eDdAdyacente



89/124


89

5][

6][

1][

6][

4][

4][

2][

0][

$%&

=

==

=

=

=

=

=

=

hD

gD

fD

eD

dD

cD

bD

aD

geT

{ 6$65%6min&][a =+=gDhAdyacente



90/124


90

5][

6][

1][

6][

4][

4][

2][

0][

$%&

=

==

=

=

=

=

=

=

hD

gD

fD

eD

dD

cD

bD

aD

geT



91/124

!o os de 4 a os o ! dos=boles /bacadoes de Costo 5%nimo

7ea G - (V,A) un !a"o cone:o en donde cadaaista (u,v) deAtiene un costo asociado c(u,v)&

n bol abacado de G es un bol libe queconecta todos los 'tices de V, su costo es la

suma de los costos de las aistas del bol& 7e quiee obtene el bol abacado de costo m%nimo

paa G&

na aplicacin t%pica de los boles abacadoes decosto m%nimo tiene lu!a en el diseAo de edes decomunicacin& n bol abacado de costo m%nimo epesenta una ed

que comunica todas las ciudades a un costo minimal&

91



92/124

/l!oitmos de 4a"os No ii!idos =boles /bacadoes de Costo 5%nimo (cont&)

?ay di"eentes maneas de constui un bolabacado de costo m%nimo&

5uc6os mtodos utili;an la popiedadAA5& 7ea G- (V,A) un !a"o cone:o con una "uncin de

costo de*nida en las aistas& 7ea 6 al!8n subcon#unto popio del con#unto de

'tices V& 7i (u,v) es una aista de costo m%nimo tal que u

6 y v V,6, e:iste un bol abacado de costom%nimo que incluye (u,v) ente sus aistas&

92



93/124

! !/l!oitmo de Pim

El algorit-o de ,ri-es un al!oitmo de la teo%ade los !a"os paa enconta un bol abacado decosto m%nimo en un !a"o cone:o, no dii!ido y

cuyas aistas estn etiquetadas& En otas palabas, el al!oitmo encuenta un

subcon#unto de aistas que "oman un bol contodos los 'tices, donde el peso total de todas las

aistas en el bol es el m%nimo posible& 7i el !a"o no es cone:o, entonces el al!oitmo

enconta el bol abacado de costo m%nimo paauno de los componentes cone:os que "oman dic6o!a"o no cone:o&

93



94/124

! !/l!oitmo de Pim (cont&)

El al!oitmo "ue diseAado en S9po el matemtico o#tec6 `aniD y

lue!o de manea independiente poel cient%*co computacional @obet C&Pim en S y edescubieto po

i#Dsta en SS& Po esta a;n, el al!oitmo es

tambin conocido como algorit-oD;, o algorit-o de ;arni6&

94



95/124


El al!oitmo comien;a cuando se asi!na a uncon#unto 6un 'alo inicial (un 'tice del !a"o), enel cual UceceV un bol abacado, aista poaista&

En cada paso locali;a la aista ms cota (u,v) queconecta los 'tices, y despus a!e!a uen 6&Este paso se epite 6asta que 6- V&

E#emplo en el Reb+

6ttp+33BBB&dma&*&upm&es3#a'a3matematicadisceta3_usDal]


96/124


E#emplo+ Enconta el bol abacado de costo

m%nimo del si!uiente !a"o no dii!ido

utili;ando el al!oitmo de Pim&

96



97/124


97

$ v V 6 V,6

QQQ.,G,,Z,,

\1.1

.G,,Z,,\1

624

663

255

46551356

516

6

5

4

32

1

654321



98/124


98

$ v V 6 V,6

QQQ.,G,,Z,,

\1.1

.G,,Z,,\1

.(,)1 .,G,,Z,,

\1.,1 .G,Z,,\1

624

663

255

46551356

516

6

5

4

32

1

654321



99/124

/l!oitmo de Pim (cont&)

99

$ v V 6 V,6

QQQ.,G,,Z,,

\1.1

.G,,Z,,\1

.(,)1 .,G,,Z,,

\1.,1 .G,Z,,\1

.(,),(,\)1 \.,G,,Z,,

\1.,,\1 .G,Z,1

624

663

255

46551356

516

6

5

4

32

1

654321



100/124


100

$ v V 6 V,6

QQQ.,G,,Z,,

\1.1

.G,,Z,,\1

.(,)1 .,G,,Z,,

\1.,1 .G,Z,,\1

.(,),(,\)1 \.,G,,Z,,

\1.,,\1 .G,Z,1

.(,),(,\),(\,Z)1 Z.,G,,Z,,

\1.,,Z,\1 .G,1

624

663

255

46551356

516

6

5

4

32

1

654321



101/124


101

T v V U V-U

''' &1%2%3%4%5%6$ &1$ &2%3%4%5%6$

&(1%3)$ 3 &1%2%3%4%5%6$ &1%3$ &2%4%5%6$

&(1%3)%(3%6)$ 6 &1%2%3%4%5%6$ &1%3%6$ &2%4%5$

&(1%3)%(3%6)%(6%4)$ 4 &1%2%3%4%5%6$ &1%3%4%6$ &2%5$

&(1%3)%(3%6)%(6%4)%(3%2)$ 2 &1%2%3%4%5%6$ &1%2*3%4%6$ &5$

624

663

255

46551356

516

6

5

4

32

1

654321



102/124


102

T v V U V-U

''' &1%2%3%4%5%6$ &1$ &2%3%4%5%6$

&(1%3)$ 3 &1%2%3%4%5%6$ &1%3$ &2%4%5%6$

&(1%3)%(3%6)$ 6 &1%2%3%4%5%6$ &1%3%6$ &2%4%5$

&(1%3)%(3%6)%(6%4)$ 4 &1%2%3%4%5%6$ &1%3%4%6$ &2%5$

&(1%3)%(3%6)%(6%4)%(3%2)$ 2 &1%2%3%4%5%6$ &1%2*3%4%6$ &5$

&(1%3)%(3%6)%(6%4)%(3%2)%(2%5)$ 5 &1%2%3%4%5%6$ &1%2%3%4%5%6$ &$

624

663

255

46551356

516

6

5

4

32

1

654321



103/124


103

T v V U V-U

''' &1%2%3%4%5%6$ &1$ &2%3%4%5%6$

&(1%3)$ 3 &1%2%3%4%5%6$ &1%3$ &2%4%5%6$

&(1%3)%(3%6)$ 6 &1%2%3%4%5%6$ &1%3%6$ &2%4%5$

&(1%3)%(3%6)%(6%4)$ 4 &1%2%3%4%5%6$ &1%3%4%6$ &2%5$

&(1%3)%(3%6)%(6%4)%(3%2)$ 2 &1%2%3%4%5%6$ &1%2*3%4%6$ &5$

&(1%3)%(3%6)%(6%4)%(3%2)%(2%5)$ 5 &1%2%3%4%5%6$ &1%2%3%4%5%6$ &$

624

663

255

46551356

516

6

5

4

32

1

654321



104/124


104

=

=

=

=

=

=

=

=

=

=

=

=

326130

432150

++++++

]6[

]6[

]6[

654321

&$

$6%5%4%3%2%1&

326130

432150

+++++

]5[

]5[

]5[

654321

$5&

$6%4%3%2%1&

336130

462150

++++

]4[

]4[

]4[

654321

$5%2&

$6%4%3%1&

336130

462150

+++

]3[

]3[

]3[

654321

$5%4%2&

$6%3%1&

331130

465150

++

]2[

]2[

]2[

654321

$6%5%4%2&

$3%1&

111110

5160

+

]1[

]1[

]1[

654321

$6%5%4%3%2&

$1&

P

D

M

UV

U

P

D

M

UV

U

P

D

M

UV

U

P

D

M

UV

U

P

D

M

UV

U

P

D

M

UV

U



105/124


105




106/124

/l!oitmo de _usDal(cont&)

El algorit-o de


107/124

/l!oitmo de _usDal (cont&)


108/124


/l acaba el al!oitmo, el bosquetiene una sola componente, la cual"oma un bol abacado de costo

m%nimo del !a"o& E#emplo en el Reb+

6ttp+33students&ceid&upatas&!3papa!el

3po#ect3DusDal&6tm&

108

http://students.ceid.upatras.gr/~papagel/project/kruskal.htmhttp://students.ceid.upatras.gr/~papagel/project/kruskal.htmhttp://students.ceid.upatras.gr/~papagel/project/kruskal.htmhttp://students.ceid.upatras.gr/~papagel/project/kruskal.htm


109/124


E#emplo+ Enconta el bol abacado de costo

m%nimo del si!uiente !a"o no dii!ido

utili;ando el al!oitmo de _usDal&

109



110/124


110

Costo /istas

(,)

G (Z,\)

(G,)

Z (,\)

(,Z) M (G,) M(,Z)

\ (,) M (,\)

/l!oitmos de 4a"os No ii!idos M/l i d _ D l ( )


111/124


111

Costo /istas

(,)

G (Z,\)

(G,)

Z (,\)

(,Z) M (G,) M(,Z)

\ (,) M (,\)

/l!oitmos de 4a"os No ii!idos M/l it d _ D l ( t )


112/124


112


/l!oitmos de 4a"os No ii!idos Ml i d 8 d 6


113/124

/l!oitmo de 08squeda en /nc6ua

/s'eda en anc5ra(*#o read+,frs searc+en in!ls) es un al!oitmo paa ecoe o buscaelementos en un !a"o (usado "ecuentemente

sobe boles)& >ntuiti'amente, se comien;a en la a%; (eli!iendo al!8nnodo como elemento a%; en el caso de un !a"o) y see:ploan todos los 'ecinos de este nodo&

/ continuacin paa cada uno de los 'ecinos se e:ploansus especti'os 'ecinos adyacentes, y as% 6asta que seecoa todo el bol&

7u nombe se debe a que e:pande uni"omementela "ontea ente lo descubieto y lo no descubieto&Lle!a a los nodos de distancia (, slo tas 6abelle!ado a todos los nodos a distancia (Q&113

/l!oitmos de 4a"os No ii!idos M/l it d 08 d / 6 ( t )


114/124

/l!oitmo de 08squeda en /nc6ua (cont&)


115/124


uante un ecoido en anc6ua, cuando seecoen cietas aistas, lle'an a 'tices sin 'isita&

Las aistas que lle'an a 'tices nue'os se conocen

como aristas de r1oly "oman un 1os'ea1arcador en anc5rapaa el !a"o no dii!idodado&

/dems, e:isten un tipo de aista de*nido po una

b8squeda en po"undidad de un !a"o no dii!ido,que se conocen como+ Aristas cr2adas:Es la aista que e:iste ente un

'tice a oto, peo que se llama de manea indiecta,peo el 'tice no es anteceso del oto&

115



116/124


E#emplo+ @eali;a el ecoido en anc6ua (si!a el

oden al"abtico) y enconta el bosque

abacado del si!uiente !a"o nodii!ido&

116



117/124


117

/l!oitmos de 4a"os No ii!idos


118/124

/l!oitmos de 4a"os No ii!idos M/l!oitmo de 08squeda en /nc6ua (cont&)

Pseudocdi!o delal!oitmo+

118

/l!oitmos de 4a"os No ii!idos M/l it d 08 d P " did d


119/124

/l!oitmo de 08squeda en Po"undidad

n recorrido en 4rofndidad(en in!ls D7SQDe-+ *irs #earc+) es un al!oitmo que pemiteecoe todos los nodos de un !a"o o bol de

manea odenada, peo no uni"ome& 7u "uncionamiento consiste en i e:pandiendo

todos y cada uno de los nodos que 'a locali;ando,de "oma ecuente, en un camino conceto&

Cuando ya no quedan ms nodos que 'isita endic6o camino, e!esa, de modo que epite elmismo poceso con cada uno de los 6emanos delnodo ya pocesado&

119

/l!oitmos de 4a"os No ii!idos M/l!oitmo de 08squeda en Po"undidad (cont )


120/124

/l!oitmo de 08squeda en Po"undidad (cont&)

uante un ecoido en po"undidad, cuando seecoen cietas aistas, lle'an a 'tices sin 'isita&

Los acos que lle'an a 'tices nue'os se conocen

como aristas de r1oly "oman un 1os'ea1arcador en 4rofndidad paa el !a"o nodii!ido dado&

/dems, e:isten un tipo de aista de*nido po una

b8squeda en po"undidad de un !a"o no dii!ido,que se conocen como+ Aristas de retroceso:Es la aista que e:iste ente un

'tice a oto, peo que se llama de manea indiecta,que es su anteceso&

120



121/124


E#emplo+ @eali;a el ecoido en po"undidad

(si!a el oden al"abtico) y enconta el

bosque abacado del si!uiente !a"odii!ido&

121



122/124


122

/l!oitmos de 4a"os No ii!idos M/l!oitmo de 08squeda en Po"undidad


123/124

! q(cont&)


123

@e"eencias 0iblio!*cas


124/124

@e"eencias 0iblio!*cas

/6o, ?opco"t llman& UEstuctuasde atos y /l!oitmosV& Peason M/ddison Resley Lon!man, Pimea

Edicin, SS& RiDipedia& @L+6ttp+33es&BiDipedia&o!&
http://es.wikipedia.org/http://es.wikipedia.org/

Documents

Teoria de Grafos 1