Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
4
1.KLASYCZNEKOLOROWANIEGRAFÓW
DEFINICJA1.9.ZespoleniemG1×G2dwóchgrafówG1iG2nazywamy
grafzawierającywszystkiewierzchołkiikrawędziegrafówG1iG2
orazdodatkowokrawędziemiędzykażdymwierzchołkiemzG1iG2.
DEFINICJA1.10.PokolorowaniemwierzchołkowymgrafuG=(V,E)nazy-
wamytakąfunkcjęc:V→N,żedowolnedwasąsiedniewierzchołki
u,υ∈Votrzymująróżnekolory,tj.{u,υ}∈E=⇒c(u)/=c(υ).
Funkcjęcbędziemynazywaćfunkcjąkolorującą.GrafG,dlaktórego
istniejepokolorowaniewierzchołkoweużywającekkolorów,nazywa-
myk-barwnym(k-kolorowalnym),atakiepokolorowaniek-pokolo-
rowaniem.Funkcjakolorującagenerujewtakimprzypadkupodział
grafuGnaniezależnepodzbioryV1,V2,
...,Vk,takieżeVi∩Vj=/
0
iV1∪V2∪...∪Vk=V.
DEFINICJA1.11.Najmniejsząliczbęk,dlaktórejistniejek-pokolorowanie
grafuGnazywamyliczbąchromatycznągrafuGioznaczamyχ(G).
Graftakibędziemyokreślaćjakok-chromatyczny,natomiastkażde
k-pokolorowanie,takieżek=χ(G),będziemynazywaćchromatycz-
nym.
JeżeliGjestczęściowopokolorowany,tostopieńnasyceniawierz-
chołkalubstopieńsaturacyjnyρ(υ)wgrafieGbędzieoznaczaćliczbę
różnobarwnychsąsiadówwierzchołkaυ.
1.1.1.
Rodzinygrafów
Wdalszymciągurozdziałubędąsiępojawiaćodniesieniadozbiorówgra-
fówopewnejokreślonejstrukturze,wykazującychinteresującecechy.Tu
przypomnimybądźpodamydefinicjeciekawszychlubbardziejegzotycz-
nychrodzingrafów.
DEFINICJA1.12.Grafemregularnymstopniar(lubgrafemr-regularnym)
będziemynazywaćgraf,wktórymwszystkiewierzchołkimająsto-
pieńr.Grafemkubicznymnazywamygrafregularnystopnia3.Hi-
perkostkąQrnazywamygrafr-regularny,któryma2rwierzchołków
odpowiadającychwszystkimciągomzero-jedynkowymdługościroraz
r2r−1krawędziłączącychtewierzchołki,którychciągiróżniąsięna
dokładniejednejpozycji.
DEFINICJA1.13.CyklemCnnazywamyn-wierzchołkowygrafspójny,re-
gularnystopnia2.KołemWnnazywamygrafpowstałyzzespolenia
dwóchgrafów:cykluCn−1orazpojedynczegowierzchołka.Ścieżka
PnjestgrafemCnbezjednejkrawędzi.GwiazdąSnnazywamypełny
