Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.4.Reprezentacjagrafu–listasąsiedztwa
29
Wprzypadkugrafówniezorientowanychsymbolemadj(v)oznaczamyzbiórwierz-
●
2.4.Reprezentacjagrafu–listasąsiedztwa
chołkówsąsiadującychzwierzchołkiemv.Wprzypadkugrafuzorientowanegomamy
doczynieniazdwomazbiorami:adj+(v)-listawierzchołkówpołączonychzvołu-
kachskierowanychodwierzchołkaviadj
-(v)-listawierzchołkówpołączonychzv
ołukachskierowanychdowierzchołkav.
Wprzypadkukomputerowejreprezentacjigrafuwygodnewużyciusątzw.listy
sąsiedztwa.Listasąsiedztwagrafuniezorientowanegotozbiórlistsąsiedztwawierz-
chołków:
{vÎV:adj(v)}.
(2.10)
Przykładowo,listasąsiedztwagrafuzrys.2.1będziewyglądałanastępująco:
1:2,4
2:1,3,5,6
3:2,4,5,6
4:1,3,5,6
5:2,3,4
6:2,3,4
Mamydoczynieniazgrafemniezorientowanym,więckażdajegokrawędźpoja-
wiasięnadwóchlistach.Zapotrzebowanienapamięćlistsąsiedztwajestoszczędne,
proporcjonalnedoliczbywierzchołkówikrawędzigrafu,tzn.jestrzęduO(n+q).
Równieprostejestokreśleniestopniawierzchołka.Bardziejkłopotliwejestsprawdze-
nie,czywgrafiewystępujekrawędźmiędzywierzchołkamiu,v.Należyprzejrzeć
listęsąsiedztwawierzchołkauwposzukiwaniuwierzchołkav.Wnajgorszymprzy-
padkujesttoczasrzęduO(D(G)).
Grafzorientowanymożnareprezentowaćzapomocąjednejzdwóchlistsą-
siedztwa
{vÎV:adj
+(v)}lub{vÎV:adj-(v)}.
Dlagrafuzrys.1.16listywyglądająnastępująco:
1:2,3,5
2:3,5,6
3:6
4:1,2,3,5,6
5:3,6
6:1
1:4,6
2:1,4
3:1,2,4,5
4:
5:1,2,4
6:2,3,4,5
Każdazlistwsposóbjednoznacznyidentyfikujestrukturępołączeńwgrafiezo-
rientowanym,analiściegrafukażdyłukwystępujejednokrotnie.
