Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.1.Pojęciapodstawowe,elementyteoriigrafów
A
0,8
0,3
C
D
0,3
0,8
B
23
ObieprzedstawionenatymrysunkudrogizwierzchołkaAdowierzchołkaBsą
złożonezdwóchkrawędzi.Pierwszaznichbiegniewzdłużkrawędziodużychwa-
gach,adrugawzdłużkrawędziowagachznaczniemniejszych.Zadającpytanie,jak
dalekojestzAdoB,musimywziąćpoduwagęto,jakirzeczywistyobiektjestre-
prezentowanyprzeznasząsieć.Jeśliwagireprezentująodległościwkilometrach,to
niewątpliwiedrogaA–D–Bjestkrótsza.Wtakichsieciachodległośćd(AjB)będzie
więcsumąwag(sumąelementówmacierzysąsiedztwa)wzdłużtejdrogi.
Rysunek2.3.Sieć30połączeńlotniczychonajwiększymruchupasażerskim
wStanachZjednoczonychwczwartymkwartale2007[290].Węzły(lotniska)onaj-
większychstopniachznajdująsięwNowymJorkuiwChicago
Możemyjednakrównieżwyobrazićsobie,żebadanasiećjestsieciątranspor-
tową,wktórejwagikrawędzimówiąoczęstościpołączeńlotniczychmiędzyróżnymi
miastami(przykładtakiejsieciprzedstawiononarysunku2.3).Intuicyjnieczujemy
wtedy,żeznacznieszybciejdostaniemysiędomiastaB,korzystajączdrogiwiodą-
cejprzezportlotniczyC.Wtakichsytuacjachmówimyzwykle:nlepiejcibędzie,
jeślipoleciszprzezC,anieprzezD”
.Wtymwypadku,abyobliczyćefektywną
odległośćd(AjB),powinniśmysumowaćraczejodwrotnościwag(odwrotnościele-
mentówmacierzysąsiedztwa).Takiepodejściemajeszczejednązaletę.Wyobraźmy
sobieizolowanywęzełE,tzn.węzełniepołączonyzżadnyminnymwęzłem.Jakpo-
liczyćodległośćmiędzynimadowolnyminnymwęzłemFnależącymdotejsamej
sieci?
E
F
E
0,0
F
