Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
26
2.Podstawowewłasnościgrafów
Mówimy,żegrafG
a=(V
a,E
a)jestpodgrafemgrafuG=(V,E)wtedy,gdyV
aÌV
orazE
aÌE.GrafemczęściowymG
b=(V
b,E
b)grafuGjestpodgraftaki,żeV
bÌV.
PodgrafemindukowanymG[V
c]przezzbiórV
cnazywamypodgrafG
c=(V
c,E
c)taki,
żeE
cmawszystkiekrawędziezbioruE,któremożnarozpiąćnawierzchołkachze
zbioruV
c.Narysunku2.3sązilustrowanewprowadzonewyżejpojęcia.PodgrafG
c
jestindukowanyprzezzbiórwierzchołków{1,2,3,4,5}.
Rys.2.3.a)GrafG;b)podgraf;c)grafczęściowy;d)podgrafindukowany
Grafniezorientowany,wktórymstopniewszystkichwierzchołkówsąiden-
tyczned(v)=d,nazywamygrafemregularnymstopniad.Zorientowanygrafregu-
larnystopniadtotakigraf,żedlakażdegowierzchołkavÎVzachodzi
d+(v)=d
–(v)=(v)=d.Przykładygrafówregularnychsąpokazanenarys.1.5
i1.15.Innymprzykłademjestgrafpusty,czylitaki,żestopniewszystkichwierz-
chołkówsąrównezeru(tzn.E=f).
Grafzupełny(nazywanyrównieżpełnym)jesttografzawierającynajwiększą
możliwąliczbękrawędziwdanejklasiegrafów.Najczęściejrozpatrywanesągrafy
zupełnewklasiegrafówzwyczajnych.Grafzupełny,zwyczajnyonwierzchołkach
oznaczamysymbolemK
nijesttografregularnystopnian-1.K
1jestnazywany
