Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1.PODSTAWOWEPOJĘCIAIDEFINICJE
3
RYSUNEK1.1.Przykładmaksymalnejkliki
(wierzchołkiobwiedzionegrubąlinią)oraz
maksymalnegozbioruniezależnego
(wierzchołkibiałe)
DEFINICJA1.6.ZbioremniezależnymwgrafieGnazywamypodzbiór
V/⊆V,takiżeu,υ∈V/=⇒{u,υ}/
∈E.ZbiórniezależnyV/wgrafie
Gnazywamymaksymalnym,jeżelinieistniejeżadenzbiórniezależny
V//,takiżeV/⊂V//(patrzrys.1.1).Liczbąstabilnościα(G)nazywa-
myrozmiarnajwiększegozbioruniezależnego.
DEFINICJA1.7.GrafGnazywamyk-dzielnym(k>1),jeżelizbiórje-
gowszystkichwierzchołkówmożnapodzielićnakpodzbiorówV1,
V2,
...,Vkwtakisposób,żekażdakrawędźgrafuGłączydwawierz-
chołkizróżnychpodzbiorów(patrzrys.1.2).Grafk-dzielnynazywa-
mypełnym,jeżelidowolnywierzchołekυjestsąsiednizewszystkimi
wierzchołkaminienależącymidotegosamegozbioruniezależnego,
doktóregonależyυ.Jeżeli|Vi|=nidlai=1,2,
...,k,topełnygraf
k-dzielnyoznaczamysymbolemKn
1,n2,...,nk.Jeżelidodatkowoni=1
dlakażdegoi,topełnygrafk-dzielnyzapisujemyjakoKk.
RYSUNEK1.2.Przykładygrafów:(a)dwudzielnego,(b)trójdzielnego
DEFINICJA1.8.RdzeniemgrafuGnazywamypodgrafuzyskanyprzezsuk-
cesywneusuwaniezgrafuGwszystkichwierzchołkówstopnia1(patrz
rys.1.3).
RYSUNEK1.3.Przykładrdzeniagrafu
(wierzchołkibiałe)
