W-Algorytmy teorii grafow AGR.pdf

ALGORYTMYTEORIIGRAF ¶ OW(AGR320).CZE , ¶ S ¶ CI.

semestrletni2004/2005

1.1.Algorytmy.

Ka_zdyalgorytmmusimie¶cpie , ¶cwa_znychcech[Knuth, TheArtofCom-

puterProgramming ,strona4]:

² sko¶nczono¶s¶c

² jednoznaczno¶s¶ciprecyzyjno¶s¶cwszystkichkrok¶ow

² okre¶slonewej¶scie

² okre¶slonewyj¶scie

² efektywno¶s¶c

Algorytmmo_znawyrazi¶cwr¶o_znychpostaciach:krokimoga , by¶copisane

werbalnie,mo_zeonby¶cwformieprogramukomputerowegonapisanego

szczeg¶oÃlowowje , zykuzrozumiaÃlymprzezstosowana , maszyne , ,lubte_z

algorytmmo_zeprzyja , ¶cposta¶cpo¶srednia , mie , dzytymidwomaprzypad-

kamiskrajnymi{schematblokowy.

1.2.PrzeszukiwaniegrafuwgÃla , biwszerz.

Istnieja , dwanaturalnesposobyprzeszukiwaniakrawe , dzigrafuprzy

poruszaniusie , odwierzchoÃlkadowierzchoÃlka:

I.Znajduja , csie , wpewnymwierzchoÃlku v (badaja , ctenwierzchoÃlek)

przeszukujemywszystkiekrawe , dzieincydentnedo v ,anaste , pnie

badamyjeszczeniezbadanewierzchoÃlkiprzylegÃledo v {poruszamy

sie , dopewnegowierzchoÃlkaprzylegÃlego w iprzeszukujemywszys-

tkiekrawe , dzieincydentnedo w .Tenprocesprowadzisie , dota , d,

a_zzbadasie , wszystkiewierzchoÃlkiwgra¯e.Metode , te , nazywasie ,

przeszukiwaniemwszerzgrafu(ang. breadth-¯rstsearch ).

Typesetby A M S -T E X

ALGORYTMYTEORIIGRAF ¶ OW(AGR320).CZE , ¶ S ¶ CI. 1

II.Przeciwnepodej¶sciepoleganatym,_zezamiastprzeszukiwa¶cka_zda ,

krawe , d¶zincydentna , dowierzchoÃlka v ,poruszamysie , dopewnego

wierzchoÃlkaprzylegÃlego w (wierzchoÃlka,wkt¶orymdotychczasjeszcze

niebyli¶smy),gdytylkotojestmo_zliwe,pozostawiaja , cnaraziewierz-

choÃlek v zby¶cmo_zeniezbadanymikrawe , dziami.Inaczejm¶owia , c,

poda , _zamyprzezgraf¶scie_zka , przechodza , cdonowegowierzchoÃlka,

gdytylkotojestmo_zliwe.Takametodaprzeszukiwaniagrafu,zwana

poszukiwaniemwgla , b(wskr¶ocieDFS-ang. depth-¯rstsearch )lub

metoda , powrotupotejsamej¶scie_zcenagra¯e,okazaÃlasie , bardzo

u_zytecznaprzyupraszczaniuwielualgorytm¶owteoriigraf¶ow,ze

wzgle , dunaotrzymywaneponumerowaniewierzchoÃlk¶owiskierowanie

narzuconenakrawe , dzie.

OpisalgorytmuDFS.

Niech G be , dziedanymgrafemnieskierowanymwprowadzonymwposta-

cilistywierzchoÃlk¶owsa , siednich.Niech x be , dzieokre¶slonymwierz-

choÃlkiem,zkt¶oregonale_zyrozpocza , ¶cposzukiwanie, PALM i FRON

sa , dwomarozÃla , cznymipodzbiorami,nakt¶orenale_zypodzieli¶ckrawe , dzie

grafu G .

1. v := x;i :=0, PALM := ;;FRON := ;

2. i := i +1 ;NUM ( v ):= i .

3.Poszukujemynieprzebytejkrawe , dziincydentnejdowierzchoÃlka v .

(a)Je_zeliniematakiejkrawe , dzi(tzn.poka_zdejkrawe , dziincydentnej

do v ju_zprzeszli¶smy),toprzechodzimydokroku5,wprzeciwnym

razie:

(b)Wybieramypierwsza , nieprzebyta , krawe , d¶zincydentna , dowierz-

choÃlka v ,powiedzmy( v;w )iprzechodzimyja , .Ustalamyskierowa-

niekrawe , dzi( v;w )od v do w .

4.Jeste¶smyterazwwierzchoÃlku w .

(a)Je_zeli w jestwierzchoÃlkiem,wkt¶orymjeszczeniebyli¶smypod-

czastegoszukania(tzn. NUM ( w )jestnieokre¶slone),tododa-

jemykrawe , d¶z( v;w )dozbioru PALM .Podstawiamy v := w

iprzechodzimydokroku2.

(b)Je_zeli w jestwierzchoÃlkiem,wkt¶orymju_zwcze¶sniejbyli¶smy(tzn.

NUM ( w ) <NUM ( v )),tododajemykrawe , d¶z( v;w )dozbioru

2 SEMESTRLETNI2004/2005

FRON .Przechodzimydokroku3.Jeste¶smywie , czpowrotem

wwierzchoÃlku v .

5.Sprawdzamy,czyistniejejaka¶sprzebytakrawe , d¶z( u;v )wzbiorze

PALM zorientowanawkierunku v .

(a)Je_zelijesttakakrawe , d¶z,towracamysie , dowierzchoÃlka u .(Za-

uwa_zmy,_ze u jestwierzchoÃlkiem,zkt¶oregoosia , gnie , to v poraz

pierwszy).Podstawiamy v := u iprzechodzimydokroku3.

(b)Je_zeliniematakiejkrawe , dzi,toalgorytmzatrzymujesie , (jeste¶smy

zpowrotemwkorzeniu x poprzej¶sciuka_zdejkrawe , dziiodwiedze-

niuka_zdegowierzchoÃlkapoÃla , czonegoz x ).

PrzykÃlad.

Nada¶czapomoca , DFSnumeracje , wierzchoÃlkomiskierowaniekrawe , dziom

grafudanegolista , sa , siad¶ow:

a:b,e

b:a,c,d,e,f

c:b,d

d:b,c

e:a,b,f,g

f:b,e,g

g: e,f

2.1.SÃlabasp¶ojno¶s¶ciskÃladowesÃlabejsp¶ojno¶sci.

Niech v i oraz v j be , da , wierzchoÃlkamigrafu G =( V;E ).Je_zeligraf

^ G =( ^ V; ^ E )jestotrzymanyzgrafu G przypomocyoperacjiscalenia

jegowierzchoÃlk¶ow v i oraz v j ,tospeÃlniaonnaste , puja , cewarunki:

² ^ V = Vnfv i ;v j g[fzg; gdzie z=2V ,tzn.zbi¶orwierzchoÃlk¶ow ^ V

"nowego"grafuotrzymujemyzezbioruwierzchoÃlk¶ow V wyj¶sciowego

grafuusuwaja , cnajpierwscalanewierzchoÃlki v i oraz v j anaste , p-

niedodaja , cdoniegonowywierzchoÃlek z (powstaÃlyprzezscalenie

wierzchoÃlk¶ow v i ;v j ).

² ( v m ;v l ) 2Ewtedyitylkowtedy,gdy ( v m ;v l ) 2 ^ E ,gdzie m6 = i;j

i l6 = i;j tzn.wszystkiekrawe , dziegrafu G ,kt¶oreniesa , incydentne

dowierzchoÃlk¶ow v i , v j sa , r¶ownie_zkrawe , dziami"nowego"grafu ^ G .

² Je_zeli( v m ;v j ) 2E ,gdzie m6 = i;j ,to( v m ;z ) 2 ^ E ;

Je_zeli( v m ;v i ) 2E ,gdzie m6 = i;j ,to( v m ;z ) 2 ^ E ;

ALGORYTMYTEORIIGRAF ¶ OW(AGR320).CZE , ¶ S ¶ CI. 3

tzn.krawe , dzieincydentnedowierzchoÃlka z (powstaÃlegoprzezscale-

niewierzchoÃlk¶ow v i ;v j )wgra¯e ^ G odpowiadaja , krawe , dziomin-

cydentnymdowierzchoÃlka v i lubdo v j wgra¯ewyj¶sciowym G

(wzale_zno¶sciodpotrzebmo_zemytutajrozpatrywa¶clubnieroz-

patrywa¶ckrawe , dziewielokrotne)

² Je_zelirozpatrujemype , tle,to( z;z ) 2 ^ Ewtedyitylkowtedy,gdy

( v i ;v i ) 2E lub( v j ;v j ) 2E ,lub( v i ;v j ) 2E ;tzn.,_zepe , tlain-

cydentnaznowopowstaÃlymwierzchoÃlkiemzwgra¯e ^ G powstaje

wtedyitylkowtedy,gdywgra¯e G istniaÃlape , tlaincydentnazwierz-

choÃlkiem v i lubzwierzchoÃlkiem v j ,lubistniaÃlakrawe , d¶z( v i ;v j ).

Opisalgorytmu.Danyjestgraf G .Rozpoczynamyodpewnego

wierzchoÃlkawgra¯eiscalamywszystkiewierzchoÃlkiprzylegÃledoniego.

Naste , pniebierzemyscalonywierzchoÃlekizn¶owscalamyznimwszystkie

tewierzchoÃlki,kt¶oresa , terazdoniegoprzylegÃle.Processcalaniapow-

tarzamydomomentu,gdyniemo_znaju_zscali¶cwie , cejwierzchoÃlk¶ow.

Towskazuje,_zepewnasp¶ojnaskÃladowazostaÃla"scalona"dopoje-

dynczegowierzchoÃlka.Je_zelipozatymwierzchoÃlkiemniemaju_zinnych

wierzchoÃlk¶owwgra¯e,tografjestsp¶ojny.Wprzeciwnymprzypadku,

usuwamywierzchoÃlekotrzymanywwynikuscalania(zapisujemyzbi¶or

wierzchoÃlk¶ow,zkt¶orychonpowstaÃljakokolejna , skÃladowa , sp¶ojno¶sci)

irozpoczynamynasza , procedure , scalaniaoddowolnegowierzchoÃlka

wotrzymanymgra¯e.WmacierzyprzylegÃlo¶sciscalaniewierzchoÃlka

j-tegozwierzchoÃlkiemi-tymdokonujesie , zapomoca , operacjiOR,tzn.

dodanialogicznegoj-tegowierszadoi-tegowierszaorazj-tejkolumny

doi-tejkolumny.Przypomnijmy,_zewdodawaniulogicznym

1+0=0+1=1+1=1; 0+0=0 :

Naste , pniej-tywierszij-takolumnasa , usuwanezmacierzy.Zauwa_zmy,

_zepe , tlapowstaja , cazescaleniaprzylegÃlychwierzchoÃlk¶owpojawiasie ,

jakojedynkanagÃl¶ownejprzeka , tnej(mo_zemyzaka_zdymrazemzerowac

przeka , tna , ),alekrawe , dzier¶ownolegÃlesa , automatyczniezaste , powane

przezkrawe , d¶zpojedyncza , zewzgle , dunadziaÃlanieoperacjidodawania

logicznego(OR).

4 SEMESTRLETNI2004/2005

PrzykÃlad.

Znale¶z¶cskÃladowa , sÃlabejsp¶ojno¶scizawieraja , ca , wierzchoÃlek v 8 grafu

danegomacierza , przylegÃlo¶sci:

0010000001

0001010100

1000000001

0100010000

0000001010

0101000000

0000100010

0100000000

0000101001

1010000010

6 6 6 6 6 6 6 6 6 6 6 6 6 4

7 7 7 7 7 7 7 7 7 7 7 7 7 5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: