Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.1.Pojęciapodstawowe,elementyteoriigrafów
21
Definicja2.2.Stopieńkiwęzła(rząd,liczbakoordynacyjna)jesttoliczba
bezpośrednichpołączeńdanegowęzłazinnymiwęzłamiwsieci.
Węzłypołączonekrawędziąnazywamypierwszymi(najbliższymi)sąsiadami.
Naprzykładnarysunku2.2Amamyodpowiedniok1=1;k2=2;k3=4;k4=2
ik5=1.Stopieńwęzłaźwgrafieprostymmożnawyrazićjakosumęelementów
macierzysąsiedztwawkolumnielubwwierszuź:
ki=
j=1
Σ
N
aij=
Σ
j=1
N
aji.
(2.1)
Znającstopniewszystkichwęzłów,możemywyznaczyćliczbęwszystkichkrawędzi
wsieci:
E=
1
2
Σ
i=1
N
ki.
(2.2)
Możemyteżobliczyćśrednistopieńwęzła
(k>=
2E
N
.
(2.3)
Wewzorze(2.3)skorzystaliśmyztzw.lematuouściskachdłoni[308],który
mówi,żesumastopniwszystkichwęzłówwsiecijestrównapodwojonejliczbie
krawędzi(każdakrawędźmadwakońce,któredająprzyczynekdotejsumy).
Wwypadkusieciskierowanychmusimyrozróżnićstopniewejściowekinwęzła
odstopniwyjściowychkout:
kin=2
kout=3
Wsieciachskierowanychmacierzsąsiedztwaniejestsymetryczna.Ztegopo-
wodusumaelementówtejmacierzywź-tejkolumnieróżnisięodsumyelementów
wź-tymwierszu.Sumującelementymacierzysąsiedztwawzdłużkolumny,otrzymu-
jemystopieńwejściowywęzłaź,natomiaststopieńwyjściowyotrzymujemy,sumując
elementyaijwzdłużź-tegowierszatejmacierzy
k
i
in
=
j=1
Σ
N
aijj
k
i
out
=
Σ
j=1
N
aji.
(2.4)
(2.5)
