Algorytmy i struktury danych - all.pdf

(197 KB) Pobierz
Algorytmy i struktury danych - Grafy i ich reprezentacje
Algorytmy i struktury danych - Grafy i ich reprezentacje
Strona 1
sobota,06październik2007
szukaj...
Kontakt
Reklama
FAQ
Stronagłówna
Start Strukturydanych Klasyczne Grafyiichreprezentacje
templatedesignedby peekmambo.com
MENUGŁÓWNE
Start
Grafyiichreprezentacje
Strukturydanych - Klasyczne
Napisał Michał Knasiecki
czwartek,28lipiec2005
Algorytmy
Kryptografia
Napoczątekkilkadefinicji:
W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów
(wierzchołków,oznaczanych przezV)wzajemnie połącznonychzapomocą krawędzi
(oznacznychprzezE).
Grafydzielimynagrafyskierowaneinieskierowane:
Strukturydanych
Kursalgorytmiki
Praktyka
Mapaserwisu
Historiastrony
Współautorzy/CV
Rys.1.Grafnieskierowany
Rys.2.Grafskierowany
Forum
Zgłoś błąd
Jeślikrawędźłączydwawierzchołkitojestznimi incydentna .
Pętlawłasna tokrawędźłączącewierzchołekzsamymsobą.
Stopień wierzchołka wgrafienieskierowanymtoliczbaincydentnychznimkrawędzi.
Istniejekilkaalgorytmówdoprzechowaniagrafuwpamięci.
Omówmynajpierw macierzsąsiedztwa.
Budujemytablicę orozmiarachV*V,gdzieV-liczbawierzchołków.Następniewypełniamyją
zerami-jeślidwawierzchołkiniesąpołączonekrawędzią ijedynkami-jeślidwawierzchołki
są połączone.Otomacierzsąsie dztwadlagrafuzrysunku1 :
Szukaj
TaniInternetMULTIMO-
już za10złnetto.Zobacz
1 2 3 4 5
1 0 1 1 0 1
2 1 0 1 1 1
3 1 1 0 1 0
4 0 1 1 0 1
5 1 1 0 1 0
Złożoność pamięciowa O(V 2 )
Widać, żemacierzjestsymetryczna.Stosująctablicę dynamiczną możnawięczmniejszyć
rozmiarmacierzydopołowyzapisującjąjakomacierzdolno-(górno)-trójkątną.
Listaincydencji.
Należy utworzyć listę dla każdego wierzchołka v , w której przechowujemy zbiór
wierzchołkówpołączonychkrawędzią z v .Listadlagrafuzrysunku1wyglądanastępująco:
1 :2,3,5
2 :1,3,4
3 :1,2,4
4 :2,3,5
5 :4,1
2007-10-06 18:44:33
1713137.013.png 1713137.014.png 1713137.015.png 1713137.016.png 1713137.001.png 1713137.002.png
Algorytmy i struktury danych - Grafy i ich reprezentacje
Strona 2
Złożoność pamięciowaO(V+E)
Listakrawędzi jesttolista,naktórejprzechowujemywszystkiekrawędziewystępującew
grafie.
Przykładdlagrafuskierowanegozrys.2:
1-2
2-4
2-5
3-1
3-2
4-3
5-1
5-4
Zapisującprzypomocytejreprezentacjigraf,wktórymwystępują krawędzieskierowanei
nieskierowanenależywprzypadkukrawędzinieskierowanejz u do v zapisać krawędź
dwukrotnie:u-vorazv-u.
Złożoność pamięciowaO(E)
Macierzincydencji totablicaorozmiarachV*E.Składasię onazEkolumniVwierszy,
jeślikrawędź wychodzizdanegowierzchołkatopiszemywodpowiedniejkolumnie(-1),jeśli
doniegowchodzipiszemy(+1),jeśliwierzchołeknienależydokrawędzipiszemy0,jeślijest
topętlawłasnapiszemy2.
Otoprzykładdlagrafuzrys. 2.
1
2
3
4
5
1-2 -1 1
0
0
0
1-3 1 0 -1 0
0
1-5 1 0 0 0 -1
2-4 0 -1 0
1
0
2-5 0 -1 0
0
1
2-3 0 1 -1 0
0
3-4 0 0 1 -1 0
5-1 1 0 0 0 -1
5-4 0 0 0 1 -1
Złożoność pamięciowaO(E*V)
Macierzgrafu zostałaopracowanawInstytucieInformatykiPPprzezdrM.Sternę.Jestto
trochę bardziejskomplikowanareprezentacjagrafuniż poprzednie.
Należyutworzyć tablicę orozmiarach(V+2) 2 .Wierszeikolumnynumerujemyod0doV+1.
Najpierwzajmiemysię częścią macierzyograniczoną przezindeksyod1doV.Zał. żew
wierszachmamy i -tewierzchołkiawkolumnach j -tewierzchołki.Liczby,któremogą znaleźć
się naskrzyżowaniuwierzchołka i oraz j możnapodzielić na3grupy:
od1doV-istniejekrawędź skierowana: i <- j
odV+1do2*V-istniejekrawędź skierowana: i -> j
od(-V)do(-1)-brakincydentnychkrawędzi
Całysekretmacierzygrafupolegajednaknatym, żeodczytanawartość nietylkoinformuje
nas,czyistniejekrawędźłączącawierzchołki i oraz j ,alezawierateż adresnastępnego
wierzchołka,któryjestwtakiejsamejrelacjizwierzchołkiem i cowierzchołek j .
Podamterazkilkaprzykładówdlagrafuzrys.2.Liczbawierzchołkówjestrówna5.
2007-10-06 18:44:33
1713137.003.png 1713137.004.png
Algorytmy i struktury danych - Grafy i ich reprezentacje
Strona 3
Prześledzimysytuację dlawierzchołka1.wgrafiemamynastępującekrawędziezawierające
tenwierzchołek:
1 -> 2
1 <- 3
1 <- 5
Weźmypierwszą krawędź:wierzchołek2jestjedynymnastępnikiemwierzchołka1,więcw
macierzywkomórce[1,2]musimypodać adreswierzchołka2.Abyobliczyć adres
wierzchołkanr.2(mamydoczynieniaznastępnikiem)wystarczydodać doniegoliczbę
wierzchołkówwgrafie:2+5=7.Taką liczbę zapisujemywkomórce[1,2].
Przejdźmydokrawędzidrugiej:wierzchołek3jestpoprzednikiemwierzchołka1,ale(w
przeciwieństwiedonastępników)niejedynym:takżewierzchołek5jestpoprzednikiem
wierzchołka1(ostatniakrawędź nanaszejliście).Wkomórce[1,3]musimywięcpodać
adreswierzchołka5.Ponieważ jesttopoprzednik,więcadresemwierzchołka5jest5.
Przechodzimy doostatniejkrawędzi: wierzchołek5jest poprzednikiem wierzchołka,
ponieważ jestjegoostatnimpoprzednikiem(pierwszymbył wierzchołek3)wkomórce[1,5]
podajemyadreswierzchołka5,czyliznówwpisujemy5.
W naszej macierzy musimy podać także wierzchołki, które nie są połączone z
wierzchołkiem1krawędzią.Punktemwyjściowymlistytychwierzchołkówdlakażdego
wierzchołka i jestonsam(stąd:macierzgrafunienadajesię dlagrafóbzpętlamiwasnymi)
,listatazaczynasię więcwkomórce[i,i].Awięcwiemy, żewierzchołek1niejest
połączonykrawędzią zesobą samymorazwierzchołkiem4.Wkomórce[1,1]musimy
podać adreswierzchołka4,zgodnieztyumconapisałempowyżej,adresywierzchołków,
któreniesąpołączonezdanymwierzchołiekpodajesię poprzedzającnumerwierzchołka
znakiem"-".Więcwkomórce[1,1]piszemy(-4).Jednocześniewierzchołek4jestostatnim
wierzchołkiem,zktórymnie łączysię wierzchołek1,więcwkomórce[1,4]podajemyznów
adreswierzchołka4,czyli[1,4]=(-4).
Terazzajmiemysię pozostałą częścią macierzy:kolumjną nr.0i(V+1)orazwierszemnr.0
i(V+1).Beznichmożnabyjuż zapisać grafzapomocą macierzy,leczdziękinimbędziemy
mielidostępdolistypoprzednikówinastępnikówwczasieO(E).Awięc:komórka[i,0]
zawierapierwszypoprzednikwierzchołka i -tegonatomiastkomórka[0,i]ostatnipoprzednik.
W przykładzie (dotyczącym wierzchołka 1) zapiszemy [1,0]=3, [1,0]=3, ponieważ
pierwszymiostatnimpoprzednikiemwierzchołka1jest3.Podobniejestznastępnikami:
[i,V+1]rozpoczynalistę następnikówwierzchołka i -tegoa[V+1,i]kończy,awięc[1,6]=2,
[6,1]=5,gdyż pierwszymnastępnikiemwierzchołka1jest2aostatnim5.Wtensposób
wypełniliśmypierwszywierszmacierzygrafu.
Dodamjeszcze, żejeżelijakiś wierzchołekniemanastępnikówlubpoprzednikówtona
początkuikońculistyodpowiednio:następnikówlubpoprzednikówwpisujemy0.Poniżej
zamieszczamcałą macierzdlagrafuzrys.2(wkolumnachznajdują się wierzchołki j ,w
wierszachwierzchołki i ).
0 1
2
3
4
5
6
0 X 3
3
4
5
2
X
1 3 -4 7
5
-4 5
2
2 1 3
-2 3
10 10 4
3 4 7
7
-5 4
-5 1
4 2 -1 5
8
-1 5
3
5 2 9
2
-3 9
-3 1
6 X 2
5
2
3
4
X
Dlalepszegozrozumieniamacierzygrafuproponuję narysować grafnapodstawiemacierzy
isprawdzić,czyjesttografzrys.2.
Dziękidodatkowymkolumnomiwierszomzyskujemylistynastępnikówipoprzedników:
wkolumnie0:wskaźnikdopierwszegoelementunaliściepoprzedników
wwierszu0:wskaźnikdoostatniegoelementunaliściepoprzedników
wkolumnieV+1:wskaźnikdopierwszegoelementunaliścienastępników
wwierszuV+1:wskaźnikdoostatniegoelementunaliścienastępników
nagównejprzekątnej:wskaźnikdopierwszegoelementunaliścieelementównie
będącychaninastępnikamianipoprzednikami
2007-10-06 18:44:33
1713137.005.png
Algorytmy i struktury danych - Grafy i ich reprezentacje
Strona 4
Złożoność pamięciowa O((V+2) 2 )
Ostatniaaktualizacja(wtorek,18wrzesień 2007)
Mambo isFreeSoftwarereleasedundertheGNU/GPLLicense.
MobiletecMobilneSystemyInformatyczne
2007-10-06 18:44:33
1713137.006.png
Algorytmy i struktury danych - Grafy i ciąg dalszy
Strona 1
sobota,06październik2007
szukaj...
Reklama
Kontakt
Stronagłówna
FAQ
Start Strukturydanych Klasyczne Grafyiciągdalszy
templatedesignedby peekmambo.com
MENUGŁÓWNE
Start
Grafyiciągdalszy
Strukturydanych - Klasyczne
Napisał Michał Knasiecki
czwartek,28lipiec2005
Algorytmy
Kryptografia
Otododatkoweinformacjena
tematgrafów,potrzebnewbardziejskomplikowanychalgorytmach.
Kilkadefinicji:
Stopień wierzchołka -toliczbakrawędzidoniegoprzyległych
Grafregularny -tograf,wktórymkażdywierzchołekmatakisamstopień
Grafplanarny -tograf,którymożnaprzedstawić napaszczyźnietak,by żadnedwie
krawędziesię nieprzecinały
f-graf -tografzograniczonymstopniemwierzchołka,tzn.jegostopień niemożebyć
większyniż f
Grafprosty -tografbezpętliwłasnychikrawędzirównoległych
Niezmiennikgrafu -toliczbalubciągliczb,któryzależytylkoodstrukturygrafuanieod
sposobujegopoetykietowania(np.liczbawierzchołków,liczbakrawędzi)
Liczbachromatycznagrafu -tonajmniejszaliczbakolorówpotrzebnychdopokolorowania
wierzchołkówgrafutak,by żadnedwaprzyległewierzchołkiniebyłytegosamegokoloru
Przykładudopowyższychdefinicji:
Strukturydanych
Kursalgorytmiki
Praktyka
Mapaserwisu
Historiastrony
Współautorzy/CV
Forum
Zgłoś błąd
Szukaj
Taniejniebędzie!AGD,
RTV,Foto,GSM,Car
Audio.
stopień wierzchołka 1 =2,wierzchołka 2 =3,grafplanarny,f-grafdlaf=3
graf 2 -regularny,planarny
grafplanarny,f-grafdlaf=4
grafplanarny,liczbachromatycznawynosi3
Terazprzejdźmydobardzoważnegoproblemu:generowaniagrafówlosowych.
Istniejekilkamodeligrafówlosowych,omówimynajważnejsze p
2007-10-06 18:45:12
1713137.007.png 1713137.008.png 1713137.009.png 1713137.010.png 1713137.011.png 1713137.012.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin