7/24/2019 ARBPART1

1/37

5. Arbori pariali

Adeseori apar n practic probleme a cror rezolvare implicnoiuni i rezultate din teoria grafurilor. S considerm, de exemplu,

proiectarea unei reele de telecomunicaii care s conecteze un numr datde centrale, de amplasare cunoscut, astfel nct ntre oricare doucentrale s existe legtur. Unei astfel de probleme i se poate asocia ungraf neorientat n care mulimea vrfurilor este format din centralele cetrebuie interconectate, iar mulimea muciilor din perecile de centralentre care se poate realiza o legtur direct. !entru ca ntre oricare doucentrale s existe legtur, ar trebui ca graful s fie conex, dar, ca norice problem practic, intervine factorul de cost i atunci ar fi de dorits se selecteze un numr ct mai mic posibil de legturi directe ntre

centrale, cu alte cuvinte intereseaz un graf parial conex minimal algrafului, deci un arbore.

Definiie"ie # $ %&, U' un graf neorientat. (umim arbore parial al

grafului # un graf parial care este arbore.Teorem)ondiia necesar i suficient ca un graf s conin un arbore

parial este ca graful s fie conex.Demonstraie:Necesitatea !resupunem c # $ %&,U' admite un arbore parial

* $ %&, U+', U+ U. *, fiind arbore, este conex i adugnd la *muciile din UU+ el rmne conex. -eci # conex.

Suficiena !resupunem c # este conex. -ac # este conexminimal, el este arborele parial cutat. Altfel, exist o mucie x,/0Uastfel nct graful #1 $ %&, U1x,/02' este conex. -ac #1este conexminimal, arborele parial cutat este #1, altfel continum procedeul deeliminare a muciilor pn cnd obinem un graf conex minimal, care va

fi un arbore parial a lui #. 3.4.-.Observaie!rocedeul descris are un numr finit de pai, deoarece la fiecare

pas este eliminat o mucie, iar # are un numr finit de mucii. 5aimult, putem demonstra urmtoarea proprietate 6

Propoziie"ie # $ %&, U' conex, 7&7 $ n, 7U7 $ m. (umrul de mucii ce

trebuie nlturate pentru ca graful s devin un arbore este mn89

%numrul ciclomatical grafului'.Demonstraie:

178

7/24/2019 ARBPART1

2/37

!resupunem c prin eliminarea unui numr oarecare de mucii din # amobinut un graf #+ fr cicluri %o pdure'. "iecare din componenteleconexe ale lui #+ este un arbore.

(otm 6

p numrul componentelor conexe, ninumrul de vrfuri din componenta conex i, i19,:,...,p2 minumrul de mucii din componenta conex i, i19,:,...,p2.

4vident c mi $ ni9, i19,:,...,p2.(umrul de muci din #+ este

( )n n pii

p

= = 1

1

-eci au fost eliminate mn8p mucii. )nd #+ este arbore, deci conex

%p$9', numrul muciilor eliminate este mn89.3.4.-.

; prim problem, cu aplicaii, de exemplu, n cimie ar figenerarea tuturor arborilor pariali ai unui graf dat. !entru acesta vomfolosi metoda baca selectate, vom ine evidena componentelorconexe ntrun vector c de dimensiune n %n $ 7&7', ci0 desemnndcomponenta conex din care face parte nodul i, pentru i 19,:,..., n2.

Condiii interne9. Ai0 19, :, ..., m2, i 19, :, ..., n92:. Ai0 Ai890, i 19, :, ..., n:2@. c#9, Ai000 c#:, Ai000, i 19, :, ..., n92%nu se

formeaz cicluri, extremitile muciei fiind n componenteconexe diferite'.

procedure ConstrArbore (i: byte)*

*!rogramul Generare-rbori-!arialide la sfritul capitolului curent genereaz toiarborii pariali ai unui graf conex dat.

179

7/24/2019 ARBPART1

3/37

""#enereaz toi arborii pariali care au primele i-$ muc%ii""&$'()))(&i-$'!ar ": bytebe#in

if i $ n t%en""am selectat n-$ muc%ii care nu formeaz cicluri Afi&areArbore else ""selectez o muc%ie cu indice mai mare dect &i-$' for " :$ A'i*+ to m do

if c','- "**

c','- "** t%en

be#in A'i* :$ """selectez muc%ia + /nific(c','- "**- c','- "**)

""unific componentele cone,e ale e,tremitilor muc%iei + ConstrArbore(i+) 0epar(c','- "**- c','- "**)

""restaurez situaia dinaintea selectrii muc%iei + endend

niial, ci0 6$ i, i 19, :, ..., n2i apelm )onstrArbore%9'.

5.. Arbori pariali de cost minim

Uneori nu intereseaz generarea tuturor arborilor pariali ai unuigrafconex ci numai a celor care satisfac anumite condiii de optim. -eexemplu, pentru proiectarea reelei de telecomunicaii ar fi interesantobinerea unui arbore parial care s minimizeze celtuielile.

=om considera n continuare o funcie c6 U ?8, care asociaz

fiecrei mucii din graf un cost %n exemplul nostru, s spunem, distanantre dou centrale'. -efinind costul unui arbore parial ca fiind sumacosturilor muciilor arborelui, se pune problema obinerii unui arboreparial de cost minim.

-e exemplu, fie urmtorul graf6

180

7/24/2019 ARBPART1

4/37

"ig. 9.Acest graf admite mai muli arbori pariali de cost minim, de exemplu6

"ig. :.

5... Al#oritmul lui 1rus2al de determinare a unui arboreparial de cost minim3

"ie # $ %&, U' un graf conex i c6 U ?8o funcie cost. !entru

a determina un arbore parial de cost minim, se pleac de la o pdureformat din n arbori %n $ &', fiecare arbore fiind format dintrunsingur vrf. Ba fiecare pas se selecteaz o mucie de cost minim care nua mai fost selectat i care nu formeaz cicluri cu cele de>a selectate. Sconsiderm de exemplu, graful din figura 9. niial6

"ig. @.Selectnd o mucie de cost 9, obinem6

*!rogramulrus.alde la sfritul capitolului curent genereaz un arbore parial decost minim al unui graf conex, utiliznd algoritmul lui Crus

7/24/2019 ARBPART1

5/37

"ig. D.-eci am unificat arborii corespunztori extremitilor muciei

selectate. Selectm din nou o mucie de costul minim 96

"ig. E.

Ba acest pas nu mai putem selecta o mucie de cost 9, deoarecesar obine un ciclu. Selectm mucia de cost :6

"ig. F.Selectnd, n final, mucia de cost @, obinem un graf fr cicluri

maximal, deci un arbore6

"ig. G.Ba fiecare pas al algoritmului sunt unificai doi arbori, cei

corespunztori extremitilor muciei selectate. -eci, dup n9 pai,

pdurea iniial va fi transformat ntrun singur arbore.

182

7/24/2019 ARBPART1

6/37

!entru implementarea algoritmului este necesar rezolvareaurmtoarelor dou probleme6 cum extragem mucia de cost minim icum testm dac mucia selectat formeaz sau nu cicluri cu cele de>aselectate.

!entru a extrage minimul, o prim idee ar fi s sortm muciilecresctor dup cost i s parcurgem secvenial muciile ordonate. Hncazul n care arborele parial de cost minim este gsit suficient de repede,un numr mare de mucii rmn netestate i n acest caz sar pierde timpinutil cu sortarea acestor mucii. ; alt idee, mai eficient, ar fi sorganizm muciile grafului ca un mineap, structur ce permiteextragerea eficient a minimului.

!entru a testa dac o mucie formeaz cicluri cu muciile de>aselectate este suficient s testm dac extremitile muciei se gsesc n

aceeai component conex. !entru aceasta va trebui s inem permanentevidena componentelor conexe %arborilor' care se formeaz.

Reprezentarea informaiilor

9.=om memora graful ntrun vector # cu m %m $ U' componente,fiecare component fiind o nregistrare cele dou extremiti i costulmuciei6

5ucie $ record e9, e:6 =fI cost6 realI endI

:. Arborele parial de cost mimim se va memora ntrun vector A cu n9componente ce reine indicii din # ai muciilor selectate@. 4videna componentelor conexe o vom ine cu a>utorul unui vector ccu n componente, ci0 $ componenta conex creia i aparine vrful i.)omponentele conexe vor fi identificate printrun reprezentant %vrful cuindicele cel mai mic din componenta conex respectiv'.

Teorem

Algoritmul lui Crus

7/24/2019 ARBPART1

7/37

!resupunem prin reducere la absurd c arborele obinut nu estede cost minim, deci exist A+ $ %a9+, a:+, ...., an9+' un alt arbore parial,astfel nct c%A+' J c%A'.

"ie < $ min1i 7 9 i n, ai ai+2, primul indice de la care A i AK

difer.-eci A $ %a1, a2, ..., ai-1, ai, ..., an-1'

A+ $ %a1, a2, ..., ai-1, ai+, .., an-1+', cu ai ai+ .4vident c%ai' c%aj+', > 1i, ..., n92, altfel algoritmul ar fi

selectat mucia aj+ n loc de ai, deoarece ar fi avut cost mai mic i nuformeaz cicluri cu a1,...,ai-1. Adaug la A+ mucia ai. Se formeaz un ciclun care intervin doar mucii din 1ai+...an-1+2. 4limin una din muciileciclului diferit de ai. Se obine un arbore AL $ %a1,..., ai-1, ai, ai89L..., an-

1L' care are i mucii comune cu A. Hn plus c%AL'c%A+' $ c%ai'c%aj+' Mc%AL' c%A+'.?epetm procedeul de nlocuire a muciilor din A+ cu muciile

din A. ;binem c%A+' c%AL' ... c%A'.-ar am presupus c c%A+' J c%A' contradicie. -eci A este un

arbore parial de cost minim.3.4.-.

Comple,itatea al#oritmului

;rganizarea muciilor ca un mineap este de O/m0, m $ U.Algoritmul cerceteaz n cel mai defavorabil caz toate cele m muciipentru a selecta n9, la fiecare pas fiind necesar extragerea muciei decost minim, operaie de ;%log m' $ O/lo# n0. Selectarea unei muciiimplic i o operaie de unificare a doi arbori, al crei timp de execuiedepinde de metoda de unificare aleas.

5... Al#oritmul lui Prim de determinare a unui arbore

parial de cost minim3

)a i algoritmul lui Crus

7/24/2019 ARBPART1

8/37

"ig. O.Selectm o mucie de cost minim care s fie incident cu vrful E6

"ig. P.Selectm o mucie de cost minim, care s fie incident cu unul dinvrfurile din subgraful obinut la pasul anterior6

"ig. 9M.Selectez o mucie de cost 9, incident cu unul din vrfurile din subgrafulanterior6

"ig. 99.Selectnd cea de a patra mucie, obinem un arbore parial de costminim6

"ig. 9:.Ba fiecare pas se selecteaz un nou vrf, adiacent cu unul din vrfurilesubgrafului, astfel nct mucia corespunztoare s fie de cost minim.

(odul nou adugat va fi terminal i deci nu se vor obine cicluri, iar

subgraful construit este la fiecare pas conex, deci arbore.Reprezentarea informaiilor

185

7/24/2019 ARBPART1

9/37

9. ?eprezentm graful prin matricea costurilor, )nxn

C i jU

U

i j

,),

,

=

=

S||T||

LNMM

OQPP

L

N

M

M

O

Q

P

P

L

N

M

M

O

Q

P

P

, dac i,>

c% i, > dac i, >

dac0

:. Q va fi mulimea vrfurilor neselectate n subgraf %Q $ &N'.@. =om utiliza un vector

7/24/2019 ARBPART1

10/37

Algoritmul execut n9 pai, la fiecare pas selectnd un vrf dingraf de ceie minim i reactualiznd ceile vrfurilor neselectate,operaie de ;%n'. -eci algoritmul este de ordinul O/n20)

5.. Arbori pariali ;

7/24/2019 ARBPART1

11/37

#6 arra/=f0 of BistaI-eci pentru fiecare vrf din graf reinem lista vrfurilor adiacente

cu vrful respectiv.:. Arborele parial "S l reprezentm cu a>utorul unui vector T n care

pentru fiecare vrf reinem vrful din care a fost atins n timpulparcurgerii "S.T6 arra/[=f0 of =fI

@. Utilizm un vector boolean =, n care pentru fiecare vrf din grafreinem dac a fost sau nu atins n timpul parcurgerii "S.

=6 arra/=f0 of booleanID. !entru parcurgerea grafului n lime vom utiliza o coad pe care oiniializm cu vrful surs. Ba fiecare pas extragem un element dincoad, vizitm toate vrfurile nevizitate adiacente cu vrful extras i le

inserm n coad, reinnd pentru fiecare vrf vizitat vrful din care a fostatins, pentru reconstituirea arborelui parial "S.

Observaie#, T, n %numrul de vrfuri din graf' i s %vrful surs' sunt

variabile globale.procedure ;ista i: f : array' f * of booleanbe#infor i :$ to n do 'i* :$ false

C

s""iniializez coada cu vrful surs

8%ile C

'* do

be#in

4

C""e,tra#e un vrf , din coad

= :$ ,'4*

8%ile = nil do""parcur# lista de adiacen a nodului , be#in

i :$ =?.infif not 'i* t%en"" nodul i este nevizitat be#in

'i* :$ trueT'i* :$ 4""rein vrful din care a fost atins i

C

i @"introduc vrful i 7n coad

*!rogramulrbori-!ariali-56-D6de la stritul capitolului curent genereazarborii pariali "S i -"S ai unui graf conex dat.

188

7/24/2019 ARBPART1

12/37

end= :$ =?.urm

end end

endObservaii

9. -ac graful # nu este conex parcurgnd "S fiecare componentconex obinem o pdure, format din arborii pariali corespunztorifiecrei componente conexe.8) Comple,itatea algoritmului, n cazul n care graful este reprezentat

prin listele de adiacen, este de O/n9m0, unde n este numrul de vrfuri,iar m numrul de mucii din graf.

5.. Arbori pariali D

7/24/2019 ARBPART1

13/37

Algoritmul poate fi descris folosind o procedur recursiv -"S,pe care iniial o apelm cu parametrul s, astfel6

procedura DFS(x: Vf);//parcurge vrfurile nevizitate ale grafului ncepnd cu

xbe#in'4* :$ true= :$ ,'4*

8%ile =

nil do""parcur# lista de adiacen a vrfului ,

be#in i :$ =?.inf if not 'i* t%en @"i este nevizitat

be#in T'i* :$ 4""rein vrful din care a fost atins i D

7/24/2019 ARBPART1

14/37

"ig. 9F.DefiniieUn graf se numete bicone,dac nu are puncte de articulaie.Hn multe aplicaii practice, ce se pot modela cu a>utorul grafurilor,

nu sunt de dorit punctele de articulaie. ?evenind la exemplul cu reeaua

de telecomunicaii, dac o central dintrun punct de articulaie sedefecteaz rezultatul este nu numai ntreruperea comunicrii cu centralarespectiv ci i cu alte centrale.

Definiie ; component bicone, a unui graf este un subgraf biconex

maximal cu aceast proprietate.-e exemplu, pentru graful din figura 9F componentele biconexe

sunt6

"ig. 9G.!entru a descompune graful n componente biconexe vom utiliza

proprietile parcurgerii -"S. !arcurgnd graful -"S putem clasificamuciile grafului n6

mucii care aparin arborelui parial -"S %tree edges'Imucii u, v0 care nu aparin arborelui i care unesc vrful u cu

un strmo al su v n arborele parial -"S numite mucii de ntoarcere%bac< edges'. Acestea sunt marcate n exemplu punctat.

-e exemplu graful de mai sus poate fi redesenat, clasificnd muciileinnd cont de arborele parial -"S cu rdcina @6

191

7/24/2019 ARBPART1

15/37

"ig. 9O.;bservm c rdcina arborelui parial -"S este punct de articulaie

dac i numai dac are cel puin doi descendeni, ntre vrfuri dinsubarbori diferii ai rdcinii neexistnd mucii. 5ai mult, un vrf xoarecare nu este punct de articulaie dac i numai dac din orice fiu / allui x poate fi atins un strmo al lui x pe un lan format din descendeni ailui x i o mucie de ntoarcere %un drum de siguranV ntre x i /'.

!entru fiecare vrf x al grafului putem defini 6dfn/,0 =numrul de ordine al vrfului x n parcurgerea -"S a grafului%dept%-first-number'.

-e exemplu6x 0 1 2 3 4 5 6 7 8 9dn(x)

2 1 3 0 4 5 6 7 8 9

-ac x este un strmo al lui / n arborele parial -"S atuncidfn%x' J dfn%/'.

-e asemeni pentru fiecare vrf x din graf putem defini 6

lo/,0 =numrul de ordine al primului vrf din parcurgerea -"S cepoate fi atins din x pe un alt lan dect lanul unic din arborele parial-"S.

loW%x' $ min1dfn%x', min1 loW%/' 7 / fiu al lui x 2, min1dfn%/' 7 x,/0mucie de ntoarcere2.

-e exemplu6x 0 1 2 3 4 5 6 7 8 9dn(x)

2 1 3 0 4 5 6 7 8 9

192

7/24/2019 ARBPART1

16/37

!"#(x)

2 1 1 0 1 5 5 5 8 9

-eci putem caracteriza mai exact punctele de articulaie dintrun grafastfel6

x este punct de articulaie dac i numai dac este rdcina unuiarbore parial -"S cu cel puin doi descendeni sau, dac nu esterdcin, are un fiu / astfel nct loW%/' dfn%x'.

!entru exemplul din figura 9F6 nodul @ este punct de articulaie deoarece este rdcina

arborelui parial -"S i are doi descendeni, nodul G este punct de articulaie deoarece loW%O'$O dfn%G'$G, nodul E este punct de articulaie deoarece loW%F'$Edfn%E'$E,

nodul 9 este punct de articulaie deoarece loW%M'$:dfn%9'$9.5odificm procedura -"S, pentru a calcula pentru fiecare vrf dingraf valorile dfn i loW.

ntrare6graful #, reprezentat prin listele de adiacenIeire6vectorii dfn i loW.Utilizm o variabil global num, pentru a calcula numrul de ordine

al vrfului curent n parcurgerea n adncime.@@;niializarenum :$ 7

for 4 :$ to n do dfn'4* :$ Dfn>o8(s- )"" s este rdcina arborelui parial D6S

procedure Dfn>o8(u- tu: f)""parcur#e D6S #raful G 7ncepnd cu vrful u( calculnd"" valorile dfn&u' 3i lo/u02 tu este tatl lui u!ar =: >ista 4: fbe#indfn'u* :$ num lo8'u* :$ dfn'u* inc(num)= :$ ,'u*

8%ile =

nil do""parcur# lista de adiacen a lui u

be#in 4 :$ =?.inf if dfn'4* $ t%en @@4 este ne!izitat

be#inDfn>o8(4- u)

lo8'u* :$ min(lo8'u*- lo8'4*)

""funcia min returneaz minimul ar#umentelor eiend

193

7/24/2019 ARBPART1

17/37

else

if 4

tu t%en lo8'u* :$ min(lo8'u*- dfn'4*)

= :$ =?.urmend

end=om folosi aceast idee de calcul recursiv al valorilor dfn i loW

pentru descompunerea n componente biconexe a unui graf neorientatconex.

?eprezentarea informaiilor se face n acelai mod ca laparcurgerea -"S, dar vectorul = nu mai este necesar, pentru vrfurilenevizitate dfn fiind 9. Hn plus, vom folosi o stiv S n care vom reinemuciile din graf %att cele care aparin arborelui ct i cele dentoarcere' n ordinea n care sunt ntlnite n timpul parcurgerii. Atunci

cnd identificm o component biconex, mai exact identificm un nod ucare are un fiu x astfel nct loW%x' dfn%u', eliminm din stiv i afimtoate muciile din componenta biconex respectiv.

@@;niializarenum :$ 7

0

(s- )2

""stiva este iniializat cu o muc%ie fictiv &s(-$'( s fiind sursafor 4 :$ to n do dfn'4* :$

;icone4(s- )"" s este rdcina arborelui parial D6S

procedure bicone4(u- tu: f)3""afi3eaz componentele bicone,e ( parcur#nd #raful 7ncepnd"" cu vrful u2 tu este tatl lui u!ar =: >ista 4: fbe#indfn'u* :$ num lo8'u* :$ dfn'u* inc(num)= :$ ,'u*

8%ile = nil do"" parcur# lista de adiacen a lui ube#in 4 :$ =?.inf

if (tu

4) and (dfn'4* dfn'u*) t%en 0

'u- 4*

""dac tu=, sau dfn/,0

7/24/2019 ARBPART1

18/37

;icone4(4- u) lo8'u* :$ min(lo8'u*- lo8'4*)

if lo8'4*

dfn'u* t%en

""am identificat o nou component bicone,

Afisare(4- u) @@ e,tra#e din S 3i afi3eaz muc%iile""componentei bicone,e curenteelse

if 4

tu t%en lo8'u* :$ min(lo8'u*- dfn'4*)

end = :$ =?.urmend

endObservaie

;ricare dou componente biconexe au cel mult un vrf comun,deci nici o mucie nu poate fi n dou componente biconexe.

S urmrim execuia algoritmului pe urmtorul exemplu6

"ig. 9P.Arborele parial -"S este6

"ig. :M.

Eniial:

4 7 B 5 F G

dfn(4) 9 9 9 9 9 9 9 9lo8(4)

195

7/24/2019 ARBPART1

19/37

num MS6@ 9Apelez bicone4(- )

4 7 B 5 F G

dfn(4) 9 9 9 M 9 9 9 9lo8(4) M

num 9x 9

0:

@ 9@ 9Apelez bicone4(- )

4 7 B 5 F G

dfn(4) 9 9 9 M 9 9 9 9lo8(4) 9 M

num :x M0:

9 M@ 9@ 9Apelez bicone4(7- ):

4 7 B 5 F G

dfn(4) : 9 9 M 9 9 9 9lo8(4) : 9 M

num @x 9He!in n bicone4(- )

loW90 min%loW90, loWM0' =loW90loWM0 X dfn@0. Am obinut o component biconex, afiez '-7*.0:

@ 9@ 9

196

7/24/2019 ARBPART1

20/37

x :0:

9 :@ 9@ 9Apelez bicone4(- )

4 7 B 5 F G

dfn(4) : 9 @ M 9 9 9 9lo8(4) : 9 @ M

num Dx 9x D0:

: D9 :@ 9@ 9Apelez bicone4(B- )

4 7 B 5 F G

dfn(4) : 9 @ M D 9 9 9lo8(4) : 9 @ M D

num Ex :x @0:

D @: D9 :@ 9@ 9loWD0 min%loWD0, dfn@0' =M4 7 B 5 F G

dfn(4) : 9 @ M D 9 9 9

lo8(4) : 9 @ M MHe!in n bicone4(- )

197

7/24/2019 ARBPART1

21/37

loW:0min%loW:0, loWD0' =M4 7 B 5 F G

dfn(4) : 9 @ M D 9 9 9lo8(4) : 9 M M MHe!in n bicone4(- )

loW90 min%loW90, loW:0' =M4 7 B 5 F G

dfn(4) : 9 @ M D 9 9 9lo8(4) : M M M MloW90 min%loW90, dfn:0'He!in n bicone4(- )

loW@0 min%loW@0, loW90' loW90 =dfn@0.Am obinut o nou component biconex6 'B-*- '-B*- '-*- '-*.0:

@ 9x DloW@0 min%loW@0, dfnD0' =Mx E0:

@ E@ 9Apelez bicone4(5- )

4 7 B 5 F G

dfn(4) : 9 @ M D E 9 9lo8(4) 9 M M M M E

num F

x

@x F0:

E F@ E@ 9Apelez bicone4(F- 5)

4 7 B 5 F G

dfn(4) : 9 @ M D E F 9lo8(4) 9 M M M M E F

198

7/24/2019 ARBPART1

22/37

num Gx Ex G0:

F GE F@ E@ 9Apelez bicone4(G- F)

4 7 B 5 F G

dfn(4) : 9 @ M D E F Glo8(4) 9 M M M M E F G

num Ox E0:

G EF GE F@ E@ 9loWG0 min%loWG0, dfnE0' =E4 7 B 5 F G

dfn(4) : 9 @ M D E F Glo8(4) 9 M M M M E F Ex F

He!in n bicone4(F- 5)loWF0 min%loWF0, loWG0' =E4 7 B 5 F G

dfn(4) : 9 @ M D E F Glo8(4) 9 M M M M E E EloWF0 min%loWF0, dfnG0' =EHe!in n bicone4 (5- )

loWE0 min%loWE0, loWF0' =E

loWF0 X dfnE0, deci afiez o nou component biconex6'G-5*-'F-G*-'5-F*.

199

7/24/2019 ARBPART1

23/37

0:

@ E@ 9

He!in n bicone4(- )

loW@0 =min%loW@0, loWE0' =MloWE0 =dfn@0, deci afiez o nou component biconex6 '5-*.0:

@ 90top

Teorem!rocedura bicone,/s(-$0 genereaz componentele biconexe ale

grafului conex #.Demonstraie:=om lua n considerare cazul n care n, numrul de vrfuri din #,

este cel puin : %dac n = 9, # are o singur component biconex,format dintrun singur vrf'.

=om face demonstraia prin inducie dup , numrul decomponente biconexe.!%9' = 9 graful este biconex6 rdcina s a arborelui parial-"S va avea un singur fiu, sl notm x. Apelul bicone,/,( s0a explorattoate muciile grafului i lea introdus n stiva S. )um x este singurulvrf pentru care loWx0 dfns0, muciile grafului vor fi afiate ntrosingur component biconex.!%' S presupunem acum c algoritmul funcioneaz corect

pentru toate grafurile conexe cu cel mult componente biconexe.!%89' =om demonstra c algoritmul funcioneaz pentru toategrafurile conexe cu cel mult +9 componente biconexe.

"ie # un graf cu +9 componente biconexe i fie x primul vrf

pentru care este ndeplinit condiia loWx0 dfnu0. !n n acestmoment nu a fost identificat nici o component biconex. Hn urmaapelului bicone,/,( u0(toate muciile incidente cu descendeni ai lui x seafl n stiva S, deasupra muciei u, x0. )um x este primul vrf carendeplinete condiia loWx0 dfnu0, deducem c descendenii lui x nusunt puncte de articulaie. )um u este punct de articulaie, rezult cmuciile situate n S, deasupra muciei u, x0, inclusiv, formeaz ocomponent biconex. 5uciile acestei componente biconexe sunt

extrase din stiv i afiate, deci, de la acest pas algoritmul revine laaflarea componentelor biconexe ale unui graf #K, obinut din # prin

200

7/24/2019 ARBPART1

24/37

eliminarea unei componente biconexe. )um #K are componentebiconexe, conform ipotezei inductive, algoritmul determin corectcomponentele biconexe ale lui #K.

3.4.-.

ObservaieAlgoritmul de descompunere n componente biconexe a unui graf

reprezentat prin listele de adiacen este liniar %O/n+m0', unde n estenumrul de vrfuri, iar m numrul de mucii din graf.

5.5. Problem rezol!atProblema brfei-5ara+( rad $==8-

Se consider n persoane !9, !:, ..., !n care doresc fiecare s

transmit propria brfa celorlalte persoane. (umim instruciune operece %i, >' avnd urmtorul efect6 persoana !itransmite persoanei !>propria sa brf, dar i eventualele brfe primite anterior prin instruciunide la alte persoane. -in pcate anumite pereci de persoane, citite de laintrare, se dumnesc i deci nu comunic ntre ele. S se determine,dac este posibil, o secven de instruciuni prin care fiecare persoan scunoasc brfele tuturor celorlalte persoane.

Soluie6Asociem problemei un graf neorientat astfel6

mulimea vrfurilor este format din cele n persoane. ntre dou vrfuri exist mucie dac cele dou persoanecorespunzatoare comunic.

!roblema are soluie dac i numai dac graful asociat problemeieste conex.

-ac graful este conex, atunci admite un arbore parial.-eterminm un arbore parial -"S al grafului dat, cu rdcina 9.!arcurgnd acest arbore n postordine, toate brfele vor fi recepionate

de vrful 9, fiecare mucie utilizat reprezentnd o instruciune.!arcurgnd arborele n preordine, nodul 9 va transmite brfele tuturorcelorlalte persoane. Sunt astfel necesare :n: instruciuni.

Observaie (umrul de :n: instruciuni este optim.

Reprezentarea informaiilor?eprezentm graful prin matricea de adiacen6

g i j, ,

,= 01

altfel.dac i i > comunicI$

?eprezentm arborele parial -"S ca pe un arbore binar, utilizndreprezentarea fiufrate.

201

7/24/2019 ARBPART1

25/37

Utilizam un vector v de dimensiune n, pentru a marca dac un vrf afost sau nu atins n timpul parcurgerii -"S6

v i = 01,,altfel.dac i a fost vizitatI$

program barfa;const NMaxPers = 7;

type Pers = 0..NMaxPers; Arbore = ^NodArbore;

NodArbore = record

p: Pers; tata, fiu, frate: Arbore

end;var g: arrayPers, Pers! of 0..";

n, i: Pers; conex: boo#ean;

v: arrayPers! of 0.."; A: Arbore;

fout: text;

procedure citire;

var f: text; i, $: Pers;begin

assign%f, &barfa.in&'; reset%f';read#n%f, n';

for i := " to n do for $ := " to n do

gi,$! := ";

()i#e not eof%f' do

begin read#n%f, i, $'; gi,$! := 0; g$,i! := 0

end;

c#ose%f';end;

procedure *+%x: Arbore';

-viita/ varfu# x; tx este tata# #ui x

var i: Pers; 1, u: Arbore;begin

u := ni#;-u#ti/u# fiu a# #ui xfor i := " to n do

if %gx^.p, i! = "' and %vi! = 0' t)en

begin vi! := ";

ne(%1'; 1^.p := i; 1^.tata := x; 1^.fiu := ni#; 1^.frate := ni#;

if u = ni# t)en -i este pri/u# fiu a# #ui x x^.fiu := 1

e#se

u^.frate := 1; -i este pri/u# frate a# #ui u u := 1;

*+%1'; end;

202

7/24/2019 ARBPART1

26/37

end;procedure postordine%x: Arbore';

-afiseaa instructiuni#e corespunatoare parcurgerii postordinea arbore#ui *+

var 1: Arbore;

begin1 := x^.fiu;

()i#e 1 23 ni# do begin

postordine%1';

1 := 1^.frate; end;

if x23 A t)en (rite#n%fout,&%&,x^.p,&,&,x^.tata^.p,&'&';end;

procedure preordine%x: Arbore';var 1: Arbore;

beginif x 23 A t)en (rite#n%fout,&%&,x^.tata^.p,&,&,x^.p,&'&';

1 := x^.fiu;()i#e 1 23 ni# do

begin

preordine%1'; 1 := 1^.frate;

end;end;

begin -progra/ principa#citire;

assign%fout,&barfa.out&'; re(rite%fout';v"! := "; A^.p := ";

*+%A';

conex := true;for i := " to n do

if vi! = 0 t)enbegin

conex := fa#se;

brea4end;

if not conex t)en -grafu# este neconex

(rite#n%fout,&Nu exista so#utii5&' e#se begin

postordine%A';

preordine%A'; end;

c#ose%fout';end.

5.F. I4erciii

203

7/24/2019 ARBPART1

27/37

9.-emonstrai prin inducie dup numrul de vrfuri din graf calgoritmul lui !rim produce un arbore parial de cost minim.

:. "ie # $ %&, U' un graf neorientat conex. 5ucia x, /0 senumete punte dac prin eliminarea ei din graf, graful parial obinut nu

este conex. Scriei un algoritm care determin toate punile unui grafconex. Algoritmul s funcioneze n timp de ;%n8m' %n $x, m $U'.

Observaie; mucie este punte dac i numai dac nu aparine unui ciclu.@. "ie # $ %&, U' un graf neorientat conex cu funcia pondere

asociat c6 U ?8YI U &.a'. "ie T un arbore parial de cost minim pentru #. -emonstrai

c exist o mucie u, v0 T i x, /0 T astfel nct T

1u,v021x,/02este al doilea cel mai bun arbore parial de cost minim%S!1'.b'. "ie T un arbore parial pentru #. !entru oricaredou vrfuri

u, v & definim max%u, x' ca fiind o mucie de pondere maxim de pelanul unic ntre u i v n T. -escriei un algoritm cu timpul de execuie de ;%&2' astfel nct,dat T, s calculeze max%u, v', u, v &.

D. "ie # $ %&, U' un graf neorientat conex. (umim distana

dintre vrfurile x i /, notat d%x, /', numrul de mucii al celui mai scurtlan care unete x cu /.(otm6 e%x' $ excentricitatea vrfului x6

e x d x y y X

( ) %&x ( , )=

d%#' $ diametrul grafului #d G e x

x X( ) %&x ( )=

r%#' $ raza grafului #r G e x

x X

( ) %in ( )=c%#' $ centrul grafului #

c G x X e x r G( ) ( ) ( )= =n

a'. -emonstrai c c%#' este format dintrun vrf sau din douvrfuri adiacente.

b'. Artai c d%#' :Yr%#'.c'. -escriei un algoritm care s calculeze raza, diametrul i

centrul unui graf conex dat.

>) rbori pariali DS

204

7/24/2019 ARBPART1

28/37

; alt tenic de parcurgere n adncime a nodurilor unui grafeste metoda -eptSearc. Aceast metod mbin cele dou metode de

parcurgere prezentate, n sensul c urmeaz acelai algoritm ca metodareadt"irstSearc numai c utilizeaz o stiv, ca i metoda -ept

"irstSearc.-e exemplu, pentru graful din figura 9@, parcurgerea dupmetoda -S, cu nodul iniial s $ F, determin urmtoarea ordine devizitare a nodurilor6 F, D, E, O, P, 9M, 99, 9:, G, @, :, 9. 5arcnd muciileutilizate prin vizitarea nodurilor obinem un arbore parial numit arbore

parial -S, cu rdcina s $ F %figura :9'6 F,D0, F,E0, F,O0, F,P0, P,9M0,P,990, 99,9:0, 9M,G, G,@0, @,:0, :,90.

"ig. :9.Scriei un program care realizeaz parcurgerea n adncime dupa

metoda -S a unui graf, cu obinerea arborelui parial -S.F. !roblema sponsorului

%;limpiada (aional

de nformatic,

Suceava 9PPF'?ATU) Suceava, unul dintre sponsorii olimpiadei, i propune s

mbunteasc transportul n comun n localitate. -irectorul va pune ladispoziie o scem pe care sunt reprezentate staiile, numerotate pentrusimplificare, de la 9 la n i cele < linii directe ntre staii, astfel nct ntreoricare dou staii exist legtur, eventual cu scimbarea mi>locului detransport. Trebuie s determinai dac exist cel puin o linie direct prin

blocarea creia legtura, direct sau indirect, ntre cel puin dou staii

s fie ntrerupt. -ac astfel de linii exist, s se propun nfiinarea unuinumr ct mai mic de linii directe ntre staiile existente astfel nct prinblocarea unei singure linii directe, oricare ar fi aceasta, circulaia ntreoricare dou staii s fie posibilI se alege soluia pentru care sumaocolurilor pe traseele varianta %msurate n numr de linii directe' s fiect mai mic.

205

7/24/2019 ARBPART1

29/37

Ane4

program Generare_Arbori_Partiali;const NMax6f = 0;

NMaxMuc)ii = NMax6f8%NMax6f9"' div ;

type 6f = "..NMax6f; NrMuc)ie = "..NMaxMuc)ii; raf = array".., NrMuc)ie! of NrMuc)ie;

Arbore = array0..NMax6f9"! of NrMuc)ie;

var n: 6f; /: NrMuc)ie; g:raf; a: Arbore;

c: array6f! of 6f; nr: (ord; fout: text;

procedure nitia#iare;var i: NrMuc)ie; $: 6f; fin: text;

begin

assign%fin, &ap.in&'; assign%fout, &ap.out&';re(rite%fout'; reset%fin';

read#n%fin, n, /';for i := " to / do read#n%fin, g",i!, g,i!';

for $ := " to n do c$! := $;

c#ose%fin'end;

procedure crieArb;

var i: 6f;

begininc%nr';

(rite#n%fout, &Arbore#e &,nr';for i := " to n9" do

(rite%fout,&&, g",ai!!,&,&,g,ai!!,&! &';

(rite#n%fout'end;

procedure

7/24/2019 ARBPART1

30/37

c4! := Nou; aux := aux4!;

end;

7/24/2019 ARBPART1

31/37

begin gparinte! := gfiu!;

parinte := fiu; fiu := fiu8;

end

e#se fiu := /";

end;gparinte! := v;

end;

procedure

7/24/2019 ARBPART1

32/37

4 := g"!; g"! := g/!;

dec%/'; eyMin: rea#;

procedure nitia#iare;

var i, $, 4, nrv: 6f; c: rea#; fin: text;

beginassign%fin, &pri/.in&'; reset%fin';

read#n%fin, n, r';

for i := " to n do

for $ := " to n do i,$! := nf;for i := " to n do

begin i,i! := 0;

read%fin, nrv'; -nrv9nu/aru# de varfuri adiacente cu i

for $ := " to nrv do begin

-citesc varfuri#e adiacente cu i si costuri#e /uc)ii#or corespunatoare

read%fin, 4, c';

i,4! := c; end;

read#n%fin';

209

7/24/2019 ARBPART1

33/37

end;for i := " to n do

begin 4eyi! := r, i!;

pi! := r

end; := "..n!9r!; pr! := 0;

c#ose%fin';end;

procedure AfisareAPM;var i: 6f; cost: rea#;

begincost := 0;

(rite#n%&Muc)ii#e APM sunt: &';

for i := " to n do if i 23 r t)en

begin (rite%&&,pi!,&,&,i,&! &';

cost := costi,pi!!; end;

(rite#n;

(rite#n%&eyMin 3 4eyi!' t)en begin

>eyMin := 4eyi!; 6fMin := i

end;

:= 96fMin!; for i := " to n do -actua#ie c)ei#e varfuri#or din

if %i in ' and %i, 6fMin! 2 4eyi!' t)en

begin pi! :=6fMin; 4eyi! := gi, 6fMin!

end

end;AfisareAPM

end.

program Arbori_Partiali_BF_DF;

const NrMax6f = 0;type 6f = 0..NrMax6f;

@ista = ^Nod@ista;

210

7/24/2019 ARBPART1

34/37

Nod@ista = record inf: 6f;

ur/: @ista; end;

raf = array6f! of @ista;

Arbore = array6f! of 6f;var n: 6f;-nu/aru# de varfuri din graf

s: 6f;-varfu# sursa : raf;

AB, A*: Arbore;-arborii partia#i obtinuti prin parcurgere

B+, respectiv *+ 6: array6f! of boo#ean;

procedure nitia#iare;

var fin: text; i, $: 6f; p: @ista;

beginassign%fin, &graf.in&'; reset%fin';

read#n%fin ,n'; read#n%fin, s';for i := " to n do

begin i! := ni#; 6i! := fa#se;

()i#e not see4eo#n%fin' do

begin read%fin, $';

ne(%p'; p^.inf := $; p^.ur/ := i!; i! := p;

end;

read#n%fin'; end;

6s! := true;c#ose%fin';

end;

procedure *+%x: 6f';

var 1: @ista;begin

1 := x!;

()i#e 1 23 ni# do -parcurg #ista de adiacenta a #ui x begin

if not 61^.inf! t)en -varfu# 1^.inf este neviitat

begin 61^.inf! := true; A*1^.inf! := x; *+%1^.inf';

end;

1 := 1^.ur/; end;

end;

procedure B+;

type

7/24/2019 ARBPART1

35/37

var

7/24/2019 ARBPART1

36/37

end; @ista = ^Nod@ista;

Nod@ista = record v: 6f;

#eg: @ista;

end; raf = array0..NMax6f! of @ista;

var : tiva; : raf; #o(, dfn: array0..NMax6f! of 6f;

nr, n, sursa:6f; nu/: 0..NMax6f;

procedure nitia#iare;

var ns: 6f; i, $: 6f; p: @ista; fin: text;begin

assign%fin, &biconex.in&'; reset%fin';

read#n%fin, n'; read#n%fin, sursa';for i := 0 to n do

begin i! := ni#;

read#n%fin, ns'; for $ := " to ns do

begin

ne(%p'; read%fin, p^.v';

p^.#eg := i!; i! := p; end;

read#n%fin';

dfni! := 9" end;

c#ose%fin';ne(%'; ^.f := sursa; ^.t := 9"; ^.ur/ := ni#;

end;

procedure AfisareC

7/24/2019 ARBPART1

37/37

var p: @ista; 1: tiva; x: 6f;begin

dfnu! := nu/; #o(u! := dfnu!; inc%nu/';p := u!;

()i#e p 23 ni# do -parcurg #ista de adiacenta a #ui u

begin x := p^.v;

if %x 23 tu' and %dfnx! 2 dfnu!'t)en begin-insereaa in stiva /uc)ia%u,x'

ne(%1'; 1^.f := x; 1^.t := u;

1^.ur/ := ; := 1; end;

if dfnx! 2 0 t)en -x nu a /ai fost viitat begin

Biconex %x, u';

#o(u! := /in%#o(u!, #o(x!'; if #o(x! 3= dfnu! t)en -u punct de articu#atie;

a/ identificat o co/ponenta biconexa, ce contine /uc)ii#e din stiva pana #a %u,x'

AfisareC