Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
28
2.Podstawowewłasnościgrafów
Rys.2.6.Przykładyk-dzielnychgrafówzupełnych
Podgrafindukowany,będącygrafemzupełnym,nazywamykliką.Dlagrafupo-
kazanegonarys.2.3klikączterowierzchołkowąjestgrafindukowanyprzezzbiór
wierzchołków{1,3,4,5}.Klikitrójwierzchołkowesąindukowaneprzeznp.zbiory
wierzchołków{1,2,3},{1,3,4},{1,4,5},{3,4,5},{1,4,5},{1,3,5}.Zauważmy,że
każdakrawędźniebędącapętląjestklikądwuwierzchołkową.
GrafdwudzielnyzwyczajnyG=(V
1ÈV
2,E)totaki,żejegozbiórwierzchołków
Vmożnapodzielićnadwaniepuste
irozłącznepodzbioryV
1ÇV
2=f
takie,żekażdakrawędźeÎEmajedenwierzchołekkońcowywV
1ijedenwV
2.
Uogólnieniempojęciagrafudwudzielnegojestgrafk-dzielny(k=2,3,
...),wktórym
dokonujemypodziałuzbioruwierzchołkównakrozłącznychiniepustychpodzbiorów
V
1,V
...V
k,awierzchołkikońcowekażdejkrawędzinależądoróżnychpodzbiorów.
2,
Grafemk-dzielnymzupełnymnazywamygrafk-dzielnyzawierającywszystkiemoż-
liwekrawędzie.Grafk-dzielnyzupełnyolicznościachpodzbiorówwierzchołkówod-
powiednion
1,n
...,n
koznaczamysymbolem
2,
PrzykładygrafówK
2,2,K
2,3,
K
3,3,orazK
2,2,2sąpokazanenarys.2.6.
