Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.1.Pojęciapodstawowe,elementyteoriigrafów
19
Definicja2.1opisujenajprostszyobiektteoriigrafów,grafprosty.Możemy
jąrozszerzaćnawielesposobów.Jeślinaprzykładwszystkimkrawędziomgrafu
nadamykierunki,uzyskamygrafskierowany(digraf).Ukierunkowanakrawędź
A
B
będzienammówiłaotym,żewierzchołekAwpływawpewiensposóbnawierzcho-
łekB.NaprzykładpublikacjaAjestcytowanawpublikacjiB,nastronieinterne-
towejAjesthiperłączedostronyinternetowejB,czyteżosobaAjestprzełożonym
osobyB.
Zkoleimultigraftograf,wktórymmogąwystępowaćkrawędziewielokrotne
(gdydwawierzchołkisąpołączonewięcejniżjednąkrawędzią)orazpętle(czyli
krawędzie,którychkońcesąwtymsamymwierzchołku).
Możemyteżprzypisaćkażdejkrawędzipewnąwartość(wagę),reprezentującą
naprzykładprzepustowośćwsieciwodociągowejlubopornośćwsiecielektrycznej.
Otrzymamywtensposóbgrafzwagamilub,mówiącprościej,grafważony.
Wkońcumożemyteżanalizowaćtakiesieci,wktórychwierzchołkinależą
dodwóchrozłącznychzbiorów,aistniejącekrawędziełącząjedyniewęzłyzjed-
negozbioruzwęzłamizdrugiegozbioru(nigdywewnątrztegosamegozbioru).
Takiegrafynazywamygrafamidwudzielnymi.Przykłademjestsieć,wktórej
dojednegozbiorunależąaktorzy,adrugizbiórstanowiąfilmy.Krawędźłączy
obiektynależącedoobutychzbiorówwtedy,gdyaktorwystąpiłwdanymfilmie.
Narysunku2.1Apokazaliśmyfragmenttakzdefiniowanejsieciaktorów,anary-
sunku2.1B–rzutowanie(projekcję)grafudwudzielnegonazbióraktorów.Wta-
kiejprojekcjikrawędźłączydwóchaktorów,jeśliwystąpilioniwtymsamym
filmie.
A
OlafLubaszenko
BogusławLinda
DanutaStenka
CezaryPazura
Show
Quovadis
Tato
Psy
Piłkarskipoker
B
CezaryPazura
DanutaStenka
BogusławLinda
OlafLubaszenko
Rysunek2.1.A.Fragmentgrafudwudzielnego,wktórymwyróżnionozbióraktorów
orazzbiórfilmów.B.Projekcjagrafudwudzielnegonazbióraktorów
PodstawowymsposobemzobrazowaniastrukturygrafuorozmiarzeN(oczywi-
ściepozanarysowaniem)jestprzedstawieniegozapomocąmacierzykwadratowej
N×N,zwanejmacierząsąsiedztwaA.Elementyaijtejmacierzysąrówne
liczbiepołączeńmiędzywęzłemźorazj.Wwypadkugrafuprostegomacierzjest
symetryczna,ajejelementysąrówne0(brakkrawędzi)lub1(istniejekrawędź).
