Algorytmy i struktury danych - all

[ Pobierz całość w formacie PDF ]
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
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
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
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
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
[ Pobierz całość w formacie PDF ]