Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.Macierze
25
zˇmax
1˛i˛n
|bii|
zachodzi
A:=zI+Bˇ0j
więcdużaczęśćteoriiPerrona-Frobeniusadlamacierzynieujemnychprzenosi
sięnamacierzeMetzlera.Zanimjednakomówimytęteorię,wprowadzimy
klasyfikacjęmacierzynieujemnych,związanązichwłaściwościamispektralnymi.
Klasyfikacjamacierzynieujemnych
Klasyfikacjęmacierzynajłatwiejwprowadzić,posługującsięgrafamiiodpo-
wiadającymiimmacierzamisąsiedztwa.
Grafemnieskierowanymnazywamyparęzbiorów,zktórychpierwszyto
niepustyskończonyzbiórwierzchołków
{vi}
,drugizaśtozbiórkrawędzi,czyli
nieuporządkowanychparwierzchołków.Wgrafieskierowanym,zwanymteżdi-
grafem,przyjmujemy,żekrawędziesąuporządkowanymiparamiwierzchołków.
Drogąwgrafie,skierowanymbądźnie,nazywamyskończonyciągskierowa-
nychkrawędzi(
vi1jvi2
)(
vi2jvi3
)
j...j
(
vik≠1jvik
),wktórychżadenwierzchołek,
zwyjątkiembyćmożepoczątkowegoikońcowego,sięniepowtarza.Wtakim
przypadkumówimyocyklu.Oczywiście,oilewgrafiedrogęmożnaprzebyć
wobydwiestrony,ponieważzarówno(
vik≠1jvik
),jaki(
vikjvik≠1
)wyznaczają
tęsamąkrawędź,wdigrafiekierunekjestwyznaczonyjednoznacznie.Mówimy,
żegraf(bądźdigraf)jestspójny,jeślikażdaparawierzchołkówmożebyć
połączonadrogą.Wartozauważyć,żedanydigrafmożebyćniespójny,pomimo
żeodpowiadającymugraf(bezwyznaczonychkierunkówkrawędzi)jestspójny.
Wynikatozpowyższejobserwacji,żewgrafiekażdądrogęmożnaprzebyć
wobydwiestrony,czyli
vi
jestpołączonyz
vj
wtedyitylkowtedy,gdy
vj
jest
połączonyz
vi
,awdigrafietakbyćniemusi.Dlategoczęstospójnydigraf
nazywamygrafemsilniespójnym,rezerwującpojęciegrafuspójnegodlagrafów
nieskierowanych.
Macierząsąsiedztwagrafuo
n
wierzchołkachnazywamymacierz
D
=
(
dij
)
1˛i,j˛n
,gdzie
di,j
=1,gdyistniejekrawędźz
vj
do
vi
,i
di,j
=0,gdy
takiejkrawędziniema.Widzimy,żemacierzsąsiedztwagrafujestzawsze
symetryczna,wprzypadkuzaśdigrafumożebyćtodowolnamacierzzerojedyn-
kowa(przyczymprzypadek
dij
=
dji
=1interpretujemyjakistnieniedwóch
przeciwbieżnychkrawędziskierowanych).Łatwowidzimy,żedowolnąmacierz
zerojedynkowąmożemypowiązaćzdigrafemiodwrotnie,przyporządkowując
wierzchołkigrafuwskaźnikomwspółczynnikówmacierzy.Wtensposób
dij
=1
wtedyitylkowtedy,gdyistniejekrawędźzvjdovi.
Definicja1.2.
Niech
A
=(
aij
)
1˛i,j˛n
będziemacierząnieujemną,a
D
będzie
odpowiadającąjejmacierzązerojedynkową,toznaczy
dij
=1wtedyitylko
