Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2
1.KLASYCZNEKOLOROWANIEGRAFÓW
1.1.
Podstawowepojęciaidefinicje
DEFINICJA1.1.GrafemGnazywamyparęuporządkowanąG=(V,E),
gdzieVoznaczazbiórelementównazywanychwierzchołkami,aE
zbiórnieuporządkowanychparwierzchołkównazywanychkrawędzia-
mi.MoczbioruwierzchołkówVbędziemyoznaczaćn=|V|inazywać
rzędemgrafuG.Podobnie,moczbiorukrawędziEbędziemyoznaczać
m=|E|inazywaćrozmiaremgrafuG.Wierzchołkiu,υ∈Vnazy-
wamysąsiednimi(lubsąsiadami),jeżeli{u,υ}∈Eianalogicznie
niesąsiednimi,jeżeli{u,υ}/
∈E.Dwiekrawędziee,f∈Enazywa-
mysąsiednimi,jeżelie∩f/=/
0ianalogicznieniesąsiednimi,jeżeli
e∩f=/
0.
DEFINICJA1.2.Stopieńwierzchołkadeg(υ)wgrafieGoznaczaliczbękra-
wędziincydentnychdowierzchołkaυwgrafieG,tj.|{e∈E:υ∈e}|.
MaksymalnystopieńwierzchołkawgrafieGbędziemyoznaczaćprzez
∆(G),minimalnyzaśprzezδ(G).Liczbęg(G)=2m/(n(n−1))na-
zywamygęstościągrafuG.
Wdalszychrozważaniachbędziemyzajmowaćsięjedyniegrafami
prostymi,tj.nieskierowanymigrafami,któreniezawierająwielokrotnych
krawędzianipętli.
DEFINICJA1.3.Drogąłączącąwierzchołkiυ1iυkwgrafieGnazywa-
myuporządkowanyciągwierzchołkówυ1,υ2,
...,υk,takiżekażdy
wierzchołekwystępujewnimconajwyżejrazorazdlakażdegoi
zachodzi{υi,υi+1}∈E.
DEFINICJA1.4.OgrafieGrzęduconajmniej2powiemy,żejestspójny,
jeżelikażdaparajegowierzchołkówjestpołączonajakąśdrogą.Przyj-
mujemy,żegraf1-wierzchołkowyjestspójny.Odległościąwierzchoł-
kówuiυwgrafiespójnymG,oznaczonąprzezd(u,υ),nazywamy
długośćnajkrótszejdrogiłączącejwierzchołkiuorazυwtymgrafie.
Przyjmujemy,żed(u,u)=0.
DEFINICJA1.5.KlikąwgrafieG=(V,E)nazywamytakipodzbiórV/⊆V,
żeu,υ∈V/=⇒{u,υ}∈E.Pojęcieklikiutożsamiasięczęstozpod-
grafemopartymnatakimzbiorzewierzchołków.KlikęV/wgrafie
Gnazywamymaksymalną,jeżelinieistniejeżadnaklikaV//,takaże
V/⊂V//(patrzrys.1.1).Liczbąklikowąω(G)będziemynazywać
rozmiarnajwiększejmaksymalnejklikiwgrafieG.
