Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
22
2.Własnościsiecirzeczywistych
Wwypadkusieciważonych,wktórychkażdejkrawędzijestprzypisanawaga,
wprowadzonodefinicjęstopniaważonego,czylisiływęzła
si=
j=1
Σ
N
aij.
(2.6)
Definicja2.3.Siłąwęzłanazywamysumęwagkrawędziprzynależnychdo
tegowęzła.
Wteoriigrafówistniejewieledefinicji,którelaikowikojarząsięwtensam
sposób.Mamytunamyślidefinicjetrasy,ścieżki,marszrutyczyteżdrogi.Ponie-
ważwdalszejczęściksiążkiposługiwaćsiębędziemyjedynieostatnimzwymienio-
nychpojęć,przytaczaniepozostałychwydajenamsięnieuzasadnioneikrzywdzące
czytelnika,zmuszanegowtymrozdzialedoprzyswojeniawielunowychdefinicji.
Codociekliwszychodsyłamydopodręcznikówpoświęconychteoriigrafów(np.
[103,308]).
Definicja2.4.DrogąwgrafieGnazywamyciągkrawędzi{{v1,v2},{v2,v3},
...,{vn11,vn}},wktórymkonieckrawędzi{vi,vi+1}jestpoczątkiemkra-
wędzi{vi+1,vi+2}dlakażdegoź=1j...jn−2orazwszystkiekrawędzie
iwszystkiewierzchołkisąróżne.Początekkrawędzi{v1,v2}nazywamypo-
czątkiemdrogi,akonieckrawędzi{vn11,vn}końcemdrogi.Długościądrogi
nazywamyliczbętworzącychjąkrawędzi.
Wgrafieprzedstawionymnarysunku2.2Aprzykładowymidrogamimiędzy
wierzchołkami2i5są{{2,3},{3,5}}oraz{{2,4},{4,3},{3,5}}.Pierwszaznich
madługość2,adruga3.Pierwszazrozpatrywanychdrógjestjednocześnie
najkrótsządrogąmiędzytymiwierzchołkami.
Definicja2.5.Odległościąd(źjj)wierzchołkaźodwierzchołkajnazywamy
długośćnajkrótszejdrogiprowadzącejzźdoj.
Mówiącprostymisłowami,d(źjj)jestnajmniejsząliczbąkrawędzi,jakienależy
przejść,bydostaćsięzwierzchołkaźdowierzchołkaj.Owierzchołkachodległych
odsiebieoxkrawędzimówimy,żesąx-tymisąsiadami.
Sytuacjaniecosiękomplikujewwypadkusiecizwagami.Rozpatrzmynastę-
pującyprzypadek:
