W-Algorytmy teorii grafow AGR, Chomiki, Algorytmy i struktury danych
[ Pobierz całość w formacie 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 ). 0 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: 2 0010000001 0001010100 1000000001 0100010000 0000001010 0101000000 0000100010 0100000000 0000101001 1010000010 3 A= 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 [ Pobierz całość w formacie PDF ] |