Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.3.Typygrafów
25
Rys.2.2.Grafostopniachwierzchołków5,5,5,4,4,3
Zinterpretujemyotrzymanywynik.Czteryspośródsześciuwierzchołkówgrafu
mająbyćstopnia5,tzn.każdyznichmusiałbybyćpołączonyzewszystkimipozosta-
łymi.Konstrukcjęgrafurozpoczniemyodczterechwierzchołków,naktórychrozpi-
namygrafzupełny-stopieńkażdegojestrówny3.Mamyuzupełnićstopnietych
wierzchołkówdopięciu,tzn.potrzebujemyośmiukrawędziłączącychtewierzchołki
zpozostałymidwoma.Majątobyćwierzchołkitrzeciegostopnia,więcmogąndostar-
czyć”niewięcejniższeściukrawędzi.
GęstościągrafuD(G)nazywamystosunekliczbyjegokrawędzidonajwiększejmoż-
●
2.3.Typygrafów
liwejliczbykrawędzi,jakiemogąbyćrozpiętenawierzchołkachgrafu,wdanejklasie
grafów.Wklasiegrafówzwyczajnychgęstośćwyrażasięwzorem
.
(2.9)
