Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Rozdział1
Algorytmygrafowe
Grσf
G
jestdefiniowσnyjσkopσrσ
(VjE)
,gdzie
V
tozbiór
Literσturσ
wierzchołków,σ
E
tomultizbiórkrσwędziłączącychwierz-
chołkiz
V
ºDlσgrσfu
G=(VjE)
zczteremσwierzchołkσmi
[2]T7
[4]T22
ipięciomσkrσwędziσmi,przedstσwionegonσrysunku1º1σ,
[30]T3º2,6
zbiór
V={1j2j3j4}
,σ
E={(1j2)
,
(1j2)
,
(1j3)
,
(2j4)
,
(3j3)}
ºKrσwędziegrσfumogąbyćskierowσne(jσknσrysun-
ku1º1b)bądźnieskierowσne(rysunek1º1σ)ºZσrównozwierzchołkσmi,jσkikrσwędziσmi
możnσwiązσćdodσtkoweinformσcje,tσkiejσkwσgσ,kolorczydługośćºGrσfymσjąwie-
leodpowiednikówwświecierzeczywistym,cosprσwiσ,żesąonebσrdzoprzydσtnym
nσrzędziempodczσsrozwiązywσniσprσktycznychproblemówσlgorytmicznychº
Rozpσtrzmydlσprzykłσduzbiórskrzyżowσńwmieście,połączonychdrogσmiºNσtu-
rσlnejestutożsσmieniewierzchołkówgrσfuzeskrzyżowσniσmi,σkrσwędzigrσfuzdrogσ-
miºDrogimogąbyćjednokierunkowe(równowσżnekrσwędziomskierowσnym)lubdwu-
kierunkowe(równowσżnekrσwędziomnieskierowσnym)imσjąokreślonądługość(którą
możemyrównieżprzypisσćkrσwędziom)ºSkrzyżowσniσzkoleimogąmiećokreślonepo-
łożeniegeogrσficzne,któremożemyprzechowywσćwreprezentującychjewierzchołkσchº
Nσpotrzebytegorozdziσłuwprowσdzimyterσzkilkσczęstoużywσnychpojęćº
Definicja1010PętlσtodowolnIkrIwędź
(
skierowInIlUbnieskierowInI
)
prowIdzącIdo
wierzchołkI?zktóregowgchodzioInngmisłowg?jesttokrIwędźpostIci
(vjv)
?
v∈V
o
Definicja1020MultikrσwędzietoconIjmniejdwiekrIwędzieprowIdzącemiędzgtgmi
sImgmiwierzchołkImioWprzgpIdkUgrIfównieskierowIngchsątokrIwędziełączące
tęsImąpIręwierzchołków?nItomiIstwprzgpIdkUgrIfówskierowIngchjwgchodzące
ztegosImegowierzchołkIorIzwchodzącedotegosImegowierzchołkIo
Definicja1030Podgrσf
G!=(V!jE!)
grIfU
G=(VjE)
jesttotIkigrIf?dlIktórego
V!⊆V
orIz
E!⊆E
o
Definicja1040Grσfemindukowσnym
G!=G[V!]
przezzbiór
V!
zgrIfU
G=(VjE)
?
V!⊆V
?nIzgwImgpodgrIfgrIfU
G
?któregozbioremwierzchołkówjest
V!
?IdozbiorU
krIwędzinIleżąwszgstkiekrIwędzie
(ujv)∈E
?dlIktórgch
ujv∈V!
o
Krσwędźłączącąwierzchołki
u
i
v
będziemyoznσczσćprzez
(ujv)
(ewentuσlnie
u→v
),
σścieżkęprowσdzącązwierzchołkσ
u
dowierzchołkσ
v
przez
u;v
ºCyklembędziemy
nσzywσliścieżkęmσjącąswójpoczątekikoniecwtymsσmymwierzchołku(
u;u
)º
Szczególnymprzypσdkiemcyklujestcyklprosty,któryprzechodziprzezkσżdywierz-
chołekgrσfuconσjwyżejrσzºOdwołującsiędoposzczególnychwierzchołkówgrσfu,
